題目鏈接：

http://codeforces.com/contest/1095/problem/D

通過題意可知，每次輸入的兩個數(shù)一定相鄰，所有只要對每次輸入的兩個數(shù)看作是邊，通過向前星構(gòu)建無向圖，并且題意說明一定有環(huán)，所以只要對這個無向圖按照一定的方向找環(huán)，遇到重復的停止就行了。

代碼：

#include <iostream> //向前星。 #include <stdio.h> #include <cstring> using namespace std; const int inf=2e5+7; int head[inf],cnt=0; //頂點數(shù)是不用變的。 struct node {int from,to;int nxt; }arr[2*inf]; int ans[inf];void addedge(int a,int b) {arr[cnt].from=a;arr[cnt].to=b;arr[cnt].nxt=head[a];head[a]=cnt++; }int main() {memset(head,-1,sizeof(head));int n;int a,b,aa,bb;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d %d",&a,&b);if(i==0)aa=a,bb=b;addedge(a,b);addedge(b,a);}int one=1,flag=0;int thenow=2e5+7;int p=0;while(one!=1||flag==0){flag=1;//printf("%d ",one);ans[p++]=one;for(int i=head[one];i!=-1;i=arr[i].nxt){int to1=arr[i].to;if(to1!=thenow){thenow=one;one=to1;goto x;}/*for(int j=head[to1];j!=-1;j=arr[j].nxt){int to2=arr[j].to;if(to2==one)continue;else{one=to2;goto x;}}*/}x:;}if(ans[1]==aa||ans[2]==aa){for(int i=0;i<n;i++)printf("%d ",ans[i]);printf("\n");}else{for(int i=n-1;i>=0;i--)printf("%d ",ans[i]);printf("\n");}return 0; }

?

?

總結(jié)

以上是生活随笔為你收集整理的codeforces div3 D Circular Dance (链式向前星)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。