【CodeForces 504A】Misha and Forest

题

题意

有n个点，代号分别为0到n-1,然后第i个点有di个相连点，与i 相连的点的XOR sum 为si，求所有的边。

分析

知识：a^b^a=b,a^b^b=a.

把相连点为1的i存进队列，i的唯一相连点就是S。

然后得到一条边i到s，对i的相连点S，d--，s^=i，就相当于去掉i这个点。

然后再判断S的相连点d是不是1，是1则进入队列。

直到队列为空。

代码

代码语言：javascript复制

#include<cstdio>
#include<algorithm>
#include<queue>
#define N 100005

using namespace std;

int n,b;
int ex[N],ey[N],d[N],s[N];

queue<int> q;

int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i  )
    {
        scanf("%d%d",&d[i],&s[i]);
        if(d[i]==1)q.push(i);
    }
    
    while(!q.empty())
    {
        int i=q.front();
        q.pop();
        if(d[i]==1)
        {
            ex[b]=i;
            ey[b]=s[i];
            b  ;
            
            s[s[i]]^=i;
            d[s[i]]--;
            if(d[s[i]]==1) q.push(s[i]);
        }
    }
    
    printf("%dn",b);
    for(int i=0; i<b; i  )
        printf("%d %dn",ex[i],ey[i]);
    return 0;
}

sum 队列

0 人点赞