Codeforces Round #610 (Div. 2) E The Cake Is a Lie(拓扑排序)

题目链接：https://codeforces.com/contest/1282/problem/E

 

题目大意：

  有一个n边形，将其分割成n-2个三角形，给出这n-2个三角形，要求顺时针或者逆时针输出这个n边形的顶点，并且输出分割的顺序。

 

题目思路：

  首先可以发现，外面那一圈的边只出现过一次，所以n边形外围就是只出现过一次的边，然后这些边建图dfs就能得到第一个问题的答案。
  分割顺序就是一个拓扑排序，因为这是一个双向边，所以du先设成-1，有一条边就给对应的三角形+1，最后度为0就入队，然后就是正常的拓扑排序。需要特判n=3的情况，因为只有一条边出现两次，才会对它进行拓扑排序用的图建边，n=3的情况下没有出现两次的边。

 

以下是代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const int MAXN = 1e5+5;
map<pair<int,int> ,vector<int> >mp;
vector<int>v[MAXN],g[MAXN];
bool vis[MAXN];
void dfs(int u){
    cout<<u<<" ";
    int len=v[u].size();
    rep(i,0,len-1){
        int y=v[u][i];
        if(vis[y])continue;
        vis[y]=1;
        dfs(y);
    }
}
int du[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    mp.clear();
    int t,n,a,b,c;
    cin>>t;
    while(t--){
        cin>>n;
        rep(i,1,n)v[i].clear(),g[i].clear();
        mp.clear();
        rep(i,1,n-2){
            cin>>a>>b>>c;
            int x=a,y=b;
            if(x>y)swap(x,y);
            mp[make_pair(x,y)].push_back(i);
            x=a,y=c;
            if(x>y)swap(x,y);
            mp[make_pair(x,y)].push_back(i);
            x=b,y=c;
            if(x>y)swap(x,y);
            mp[make_pair(x,y)].push_back(i);
        }
        memset(du,-1,sizeof(du));
        for(map<pair<int,int> ,vector<int> >::iterator it=mp.begin();it!=mp.end();it++){
            vector<int>p=it->second;
            if(p.size()==1){
                int x=(it->first).first;
                int y=(it->first).second;
                v[x].push_back(y);
                v[y].push_back(x);
            }
            else{
                du[p[0]]++;du[p[1]]++;
                g[p[0]].push_back(p[1]);
                g[p[1]].push_back(p[0]);
            }
        }
        memset(vis,0,sizeof(vis));
        vis[1]=1;
        dfs(1);
        cout<<endl;
        if(n==3){
            cout<<1<<endl;
            continue;
        }
        queue<int>q;
        rep(i,1,n){
            if(!du[i])q.push(i);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            cout<<u<<" ";
            int len=g[u].size();
            rep(i,0,len-1){
                int y=g[u][i];
                du[y]--;
                if(!du[y]){
                    q.push(y);
                }
            }
        }cout<<endl;
    }
    return 0;
}