D.圆舞 (孩子坐成一圈)规律暴力

题目链接：http://codeforces.com/contest/1095/problem/D
题目大意：有n个孩子孩子坐成一圈。每个孩子会说出他顺时针的下两个孩子的编号(无序)。输入这个圆圈，多个可能输出一个3≤n≤2⋅10^5。

思路：当时题目翻译错了。以为输入的孩子也是没有顺序的。后来才知道第i行的孩子i的下两个孩子的编号。

所以只要确定第一二个孩子，然后同样一直暴力下去就行了。只是n=3的需要特殊处理一下。

思考：翻译很重要。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod=998244353;

struct node
{
    int a;
    int b;

}r[200005];

int e[200005];

void dfs(int n)
{
    fill(e, e+200005, 0);

    for(int i=1;i<=n;i++)
    {
        int a=r[i].a, b=r[i].b;
        if(r[a].a==b||r[a].b==b)//确定孩子i的下一个孩子编号
        {
            e[i]=a;
        }
        else
        {
            e[i]=b;
        }
    }
    printf("1 ");
    int f=e[1];
    while(f!=1)
    {
        printf("%d ",f);
        f=e[f];
    }
    printf("\n");

}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&r[i].a, &r[i].b);
    }
    if(n==3)
    {
        printf("1 2 3\n");
    }
    else
        dfs(n);

    return 0;
}