题意
https://vjudge.net/problem/CodeForces-1255C
一个长度为n的序列,给你n-2个三元组,比如p=[1,4,2,3,5],那么三元组为[1,4,2],[4,2,3],[2,3,5],其中每个三元组内的元素可以交换位置,整个三元组也可以和别的三元组整体交换位置,但不能交换不同三元组的数。求这个序列。
思路
记录每个数在所有三元组出现的次数、和每个数连了哪些数(和哪些数在一个三元组里),其中出现次数为1的肯定是序列的头或尾,因为序列可以反转(得到同样的三元组),所以随便选一个出现次数为1的数当头,然后这个数连的点中出现次数为2的就是第二个数。后面的数可以通过判断前面两个数连的数是否有相同,如果有,那么这个数就是第三个数,以此类推。
代码
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define ll long long const int N=200005; const int mod=1e9+7; const double eps=1e-8; const double PI = acos(-1.0); #define lowbit(x) (x&(-x)) int cnt[N],ans[N],vis[N]; vector<int> v[N]; int main() { std::ios::sync_with_stdio(false); int n; cin>>n; for(int i=1;i<=n-2;i++) { int a,b,c; cin>>a>>b>>c; cnt[a]++,cnt[b]++,cnt[c]++; v[a].push_back(b),v[a].push_back(c); v[b].push_back(a),v[b].push_back(c); v[c].push_back(a),v[c].push_back(b); } for(int i=1;i<=n;i++) { if(cnt[i]==1) { int flag=0; for(int j:v[i]) { if(cnt[j]==2) { ans[1]=i,ans[2]=j,vis[i]=vis[j]=1; flag=1; break; } } if(flag) break; } } for(int i=3;i<=n;i++) { int f=0; for(int j:v[ans[i-1]]) { for(int k:v[ans[i-2]]) { if(j==k&&!vis[j]) { ans[i]=j,vis[j]=1; f=1; break; } } if(f) break; } } for(int i=1;i<=n;i++) { cout<<ans[i]<<" "; } cout<<endl; return 0; }