題意
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121148.html
標籤：其他
上一篇：CodeForces - 1228C（質因數分解+貢獻法）
下一篇：資料結構---樹結構