codeforces 1282 E. The Cake Is a Lie （dfs+构造）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

题意：给的是一张平面图，是一个n边形，每次可以切一刀，切出一个三角形，最终切成n-2个三角形。题目给出所切三角形的三个顶点的编号，以及三角形的编号。问你切出的三角形顺序，以及按顺序输出原始n边形顶点的所有编号，可以逆序输出也顺序输出。

题解：有点类似拓扑排序。首先输入三角形三个点，a,b,c，统计出V[a] Xor b Xor c，同理统计V[b]，V[c]，这样可以保证V[i]的值只能是0 Xor 与i相连的两个点，即使三角形有共用边，多次Xor会消除公用边相连的点。根据这个性质，可以顺序输出所有点的编号。

那么三角形顺序怎么输出呢？首先发现如果一条边是被两个三角形公用的，那么可以依据这条边把两个三角形相连，这样把三角形作为一个节点从而形成了一个图，这个图结构是一颗树，我们就随便找一个叶子节点，从叶子节点开始dfs遍历一遍，输出三角形编号即可。

AC代码：

 #include<iostream>

 #include<vector>

 #include<cstring>

 #include<map>

 #include<algorithm>

 using namespace std;

 const int maxn = 1e+;

 int v[maxn];

 vector<int> g[maxn];

 int visit[maxn];

 void dfs(int x){ //从叶子节点开始搜索，因为叶子节点必定代表着最靠外的三角形，它的度是1

     visit[x] = ;

     for(int i = ;i<g[x].size() ;i++){

         int cur = g[x][i];

         if(visit[cur] ==) dfs(g[x][i]);

 //        dfs(g[x][i]);

     }

     cout<<x<<" ";

 }

 int main(){

     int t;cin>>t;

     while(t--){

         int n;

         cin>>n;

         for(int i = ;i<=maxn;i++){

             v[i] = ;//初始化V数组

             visit[i] = ;//初始化访问数组

             g[i].clear() ;

         }

         map<pair<int,int>,vector<int> > mp;

         for(int i = ;i<n-;i++){

             int a,b,c;

             cin>>a>>b>>c;

             if(a>b) swap(a,b);

             if(b>c) swap(b,c);

             if(a>b) swap(a,b);

             v[a]^=b,v[a]^=c;//Xor操作

             v[b]^=a,v[b]^=c;

             v[c]^=a,v[c]^=b;

             mp[{a,b}].push_back(i+);//添加一条边a,b，以及所共用的三角形i+1

             mp[{a,c}].push_back(i+);

             mp[{b,c}].push_back(i+);

         }

         int a,b;

         for(auto h:mp){

             if(h.second.size()==){ //随便找一条边，只共用一个三角形

                 a = h.first.first;

                 b = h.first.second;

             //    break;

             }

         }

         cout<<a<<" "<<b;//输出这条边

         for(int i = ;i<n-;i++){

             int t = a^v[b];//开始做Xor操作。具体可以用笔模拟一下这个过程，理解更清楚

             cout<<" "<<t;

             a = b,b = t;

         }

         cout<<endl;

         for(auto h:mp){

             if(h.second.size() == ){

                 int u = h.second[],v = h.second[];

                 g[u].push_back(v),g[v].push_back(u);//根据共用边以三角形为一个点建图

             }

         }

         dfs();

         cout<<endl;

     }

     return ;

 }