Codeforces Round #529 (Div. 3) D. Circular Dance (思维)

题意:有\(n\)个熊小孩,绕着树转圈圈,编号\(i\)的小孩可以记住\(a_{i,1}\)和\(a_{i,2}\)两个小孩,这两个小孩是顺时针相邻的,但谁前谁后不一定.现在给你每个小孩的\(a_{i,1}\),\(a_{i,2}\),要求还原序列.

题解:对于第\(i\)个小孩,我们去判断他的\(a_{i,1}\)和\(a_{i,2}\)哪个是和相邻的,然后存进答案里,这样找的话一定可以还原出原序列,具体怎么实现呢?我们可以先用\(pair\)存每个\(a_{i,1}\)和\(a_{i,2}\),然后对于第\(i\)个熊小孩,我们直接去判断他的两个\(next\)小孩,哪个的\(next\)可以是另一个,以题中所给的图为例,我们去判断\(5\)的两个\(next\)小孩\(3\)和\(2\),\(3\)的两个\(next\)是\(2\)和\(4\),包含\(5\)的一个\(next\)小孩\(2\),而\(2\)则没有,所以\(3\)是\(5\)的相邻的小孩.

代码:

int n;
vector<PII> v;
int a,b;int main() {
    //ios::sync_with_stdio(false);cin.tie(0);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d %d",&a,&b);
        v.pb({a,b});
    }    if(v.size()==3){
        printf("1 2 3\n");
        return 0;
    }
    int now=1;
    for(int i=0;i<n;++i){
        a=v[now-1].fi;
        b=v[now-1].se;
        if(v[b-1].fi==a || v[b-1].se==a){
            printf("%d ",b);
            now=b;
        }
        else{
            printf("%d ",a);
            now=a;
        }
    }    return 0;
}