本文主要是介绍Codeforces 1282 E The Cake Is a Lie —— 拓扑，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
This way
题意：
现在有一个正n边型的蛋糕，每次都会在蛋糕的点上切下一个三角形，现在给你每个三角形的三个点的下标，问你这个蛋糕下标排列的顺序以及按照什么顺序切下这些三角形的。
题解：
由于最外面的边只会出现一次，切割边会出现两次，所以我们计算每条边出现的次数，然后做一个dfs就可以求出下标排列的顺序。
我们可以发现每次切下一个三角形的时候一定有一个点在接下来只出现一次，于是我们只需要做一个拓扑排序即可。
#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
const int N=1e5+5;
map<pa,bool>mp;
struct node{int a[5];}p[N];
struct edge
{int to,next;
}e[N*2];
int cnt,head[N];
void add(int x,int y){e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt++;
}
int vis[N],deg[N];
vector<int>ans1,ans2,in[N];
void dfs(int x){ans1.push_back(x);vis[x]=1;for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(vis[ne])continue;dfs(ne);}
}
int main()
{int t;scanf("%d",&t);while(t--){ans1.clear();ans2.clear();mp.clear();cnt=0;int n;scanf("%d",&n);for(int i=1;i<=n;i++)head[i]=-1,vis[i]=0,deg[i]=0,in[i].clear();for(int i=1;i<=n-2;i++){for(int j=1;j<=3;j++)scanf("%d",&p[i].a[j]),deg[p[i].a[j]]++,in[p[i].a[j]].push_back(i);sort(p[i].a+1,p[i].a+1+3);for(int j=1;j<=2;j++)for(int k=j+1;k<=3;k++)mp[{p[i].a[j],p[i].a[k]}]^=1;}for(int i=1;i<=n-2;i++){for(int j=1;j<=2;j++)for(int k=j+1;k<=3;k++)if(mp[{p[i].a[j],p[i].a[k]}]==1)add(p[i].a[j],p[i].a[k]),add(p[i].a[k],p[i].a[j]);}dfs(1);queue<int>Q;for(int i=1;i<=n;i++)if(deg[i]==1)Q.push(i);memset(vis,0,sizeof(vis));while(!Q.empty()){int u=Q.front();Q.pop();for(auto ne:in[u]){if(vis[ne])continue;vis[ne]=1;ans2.push_back(ne);for(int i=1;i<=3;i++){deg[p[ne].a[i]]--;if(deg[p[ne].a[i]]==1)Q.push(p[ne].a[i]);}}}int sz=ans1.size();for(int i=0;i<sz;i++)printf("%d%c",ans1[i]," \n"[i==sz-1]);sz=ans2.size();for(int i=0;i<sz;i++)printf("%d%c",ans2[i]," \n"[i==sz-1]);}return 0;
}这篇关于Codeforces 1282 E The Cake Is a Lie —— 拓扑的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
