Codeforces #285 (Div. 2) C - Misha and Forest

题意

      给出一个无相无环图(树或者是森林)，给出每个节点周围节点编号个数和它周围节点的异或和，重构这棵树

思路

      首先，叶子节点的异或值肯定是他的父亲节点，这样，从叶子节点开始，从底层便能逐步推导出上层的树结构，从而得到答案

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int nMax = 100000;
const int mMax = 100000;

class edge{
public:
    int u,v,nex;
};edge e[mMax];
int k,head[nMax];
void addedge(int a,int b){
    e[k].u=a;
    e[k].v=b;
    e[k].nex=head[a];
    head[a]=k;k++;
}

int aaa[nMax],bbb[nMax];
int vis[nMax];
queue<int>que;
int main(){
    int n,i,j,a,b,c;
    while(cin>>n){
        while(!que.empty())que.pop();
        memset(vis,0,sizeof(vis));
        for(i=0;i<n;i++){
            scanf("%d%d",&aaa[i],&bbb[i]);
            if(aaa[i] == 1){
                que.push(i);
                vis[i] = 1;
            }
        }
        k = 0;
        int ans = 0;
        memset(head,0,sizeof(head));
        while(!que.empty()){
            a = que.front();
            que.pop();
            if(aaa[a]!=0){
                addedge(a,bbb[a]);
                ans ++;
                aaa[bbb[a]]--;
                bbb[bbb[a]]^=a;
            }
            if(!vis[bbb[a]]){
                if(aaa[bbb[a]]==1){
                        vis[bbb[a]] = 1;
                        que.push(bbb[a]);
                }
            }
        }
//        cout<<ans<<" dd "<<k<<endl;
        cout<<ans<<endl;
        for(i=0;i<k;i++){
            cout<<e[i].u<<" "<<e[i].v<<endl;
        }
    }
    return 0;
}