寒假训练赛Ⅰ J题

寒假训练赛Ⅰ J题"/>

寒假训练赛Ⅰ J题

J. Circular Dance

题目链接
题目大意：一群小孩围成个圈跳舞，每个孩子认识他前面两个孩子，但是并不知道谁是他下一个，要求你根据题目给出的数据求出孩子的顺序。
思路：一个孩子i认识他的下一个孩子和下下个孩子，那么i的下一个孩子必须要认识i的下下一个孩子，才能使条件成立，因此只需要每次选择i认识的其中一个孩子认识i认识的另一个孩子就好了。(简直绕口令)。
代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX=200005;
struct MAP{int to1,to2;
}map[MAX];
bool used[MAX];//用来标记以及选过的点。选过的就不必再选。 
void dfs(){int cur=1;used[1]=true;printf("1 ");//我就令起始为1，无论为哪个，最后总能得出答案。 while(true){int to1=map[cur].to1,to2=map[cur].to2;if(!used[to1]&&(map[to1].to1==to2||map[to1].to2==to2)){used[to1]=true;cur=to1;}else if(!used[to2]&&(map[to2].to1==to1||map[to2].to2==to1)){used[to2]=true;cur=to2;}else break;printf("%d ",cur);}
}
int main(){int n;scanf("%d",&n);fill(used,used+MAX,false);for(int i=1;i<=n;i++){scanf("%d%d",&map[i].to1,&map[i].to2);}dfs();return 0;
}