【CodeForces 504A】Misha and Forest

饶文津

发布于 2020-06-02 11:38:28

3320

发布于 2020-06-02 11:38:28

文章被收录于专栏：饶文津的专栏

题

题意

有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则进入队列。

直到队列为空。

代码

#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("%d\n",b);
    for(int i=0; i<b; i++)
        printf("%d %d\n",ex[i],ey[i]);
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016-02-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除

sum