Codeforces Round #383 (Div. 2), problem: (E) Arpa’s overnight party and Mehrdad’s silent entering Solution in C/C++

#include <stdio.h>
#include <string.h>

int n,a[200010],b[200010],c[200010],p[200010];
void dfs(int k,int col);

int main(void)
{
    //freopen("party.in","r",stdin);
    //freopen("party.out","w",stdout);
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        p[a[i]]=b[i];  p[b[i]]=a[i];
    }
    memset(c,0,sizeof(c));
    for(i=1;i<=n*2;i++)
        if(!c[i]) dfs(i,0);
    for(i=1;i<=n;i++)
        printf("%d %d\n",c[a[i]],c[b[i]]);
    return 0;
}

void dfs(int k,int col)
{
    c[k]=col+1;
    if(!c[((k-1)^1)+1])
        dfs(((k-1)^1)+1,col^1);
    else if(!c[p[k]]) dfs(p[k],col^1);
    else return;
}

Leave a Reply

Your email address will not be published. Required fields are marked *