CF 501C Misha and Forest 好题

　　　　　　　　　　　　　　　　C. Misha and Forest

Let's define a forest as a non-directed acyclic graph (also without loops and parallel edges). One day Misha played with the forest consisting of n vertices. For each vertex v from 0 to n - 1 he wrote down two integers, degreev and sv, were the first integer is the number of vertices adjacent to vertex v, and the second integer is the XOR sum of the numbers of vertices adjacent to v (if there were no adjacent vertices, he wrote down 0).

Next day Misha couldn't remember what graph he initially had. Misha has values degreev and sv left, though. Help him find the number of edges and the edges of the initial graph. It is guaranteed that there exists a forest that corresponds to the numbers written by Misha.

Input

The first line contains integer n (1 ≤ n ≤ 216), the number of vertices in the graph.

The i-th of the next lines contains numbers degreei and si (0 ≤ degreei ≤ n - 1, 0 ≤ si < 216), separated by a space.

Output

In the first line print number m, the number of edges of the graph.

Next print m lines, each containing two distinct numbers, a and b (0 ≤ a ≤ n - 1, 0 ≤ b ≤ n - 1), corresponding to edge(a, b).

Edges can be printed in any order; vertices of the edge can also be printed in any order.

Sample test(s)

input

output

2
1 0
2 0

input

2
1 1
1 0

output

1
0 1

Note

The XOR sum of numbers is the result of bitwise adding numbers modulo 2. This operation exists in many modern programming languages. For example, in languages C++, Java and Python it is represented as "^", and in Pascal — as "xor".

题意：

有一个森林，若干棵树，一共有n个节点，编号为0~n-1，现在对于每一个节点，给出degi,sumi

degi表示节点i的度(入度+出度)

sumi表示所有和节点i直接相连的节点的编号的xor和

输出边的数量和所有边的2个端点

(e=(u,v),则输出u v)

思路：

突破口：当节点i为叶子节点时，只有一个入度，没有出度，则degi=1,这个时候fa[i]=sumi

这个时候和fa[i]相连的边确定了1条了，则：

deg[fa[i]]--

sum[fa[i]]=change(i,sum[fa[i]])

函数change(int b,int c)的功能：

有方程式x^b=c,现在我们知道了b，c，这个函数的返回值是x

那么当deg[fa[i]]==1的时候，就说明节点fa[i]还剩下1条边没有确定，而这条边的另一个顶点就是此时的sum[fa[i]]

则fa[fa[i]]=sum[fa[i]]

对于每一个节点，degi=0时说明没有边与之相连，不用管它

degi>0，就总会有degi=1的时候，这个时候，节点i的父亲节点就确定了

但是这样有一个问题：

对于根节点root是没有父亲节点的，但是会有deg[root]==1的时刻，按照上面的想法这个时候我们给了root一个父亲节点，而实际上，我们不应该给root这个父亲节点

所以：对于节点i，满足2个条件，才可以确定父亲节点

1.deg[i]==1

2.fa[i.sum]==-1(为了防止给root父亲节点)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 
 5 using namespace std;
 6 
 7 const int maxn=(1<<16)+5;
 8 
 9 int fa[maxn];
10 struct Node
11 {
12     int deg,sum,cnt;
13 };
14 Node node[maxn];
15 
16 inline int change(int b,int c)
17 {
18     int ret=0;
19     int i=0;
20     while(b>0||c>0)
21     {
22         if((b&1)!=(c&1))
23         {
24             ret+=(1<<i);
25         }
26         b>>=1;
27         c>>=1;
28         i++;
29     }
30     return ret;
31 }
32 
33 void solve(int );
34 
35 int main()
36 {
37     int n;
38     scanf("%d",&n);
39     int tmp=0;
40     for(int i=0;i<n;i++)
41     {
42         scanf("%d %d",&node[i].deg,&node[i].sum);
43         tmp+=node[i].deg;
44         node[i].cnt=i;
45     }
46     printf("%d
",tmp/2);
47     solve(n);
48 
49     return 0;
50 }
51 
52 void solve(int n)
53 {
54     memset(fa,-1,sizeof fa);
55     queue<Node>que;
56     while(!que.empty())
57         que.pop();
58     for(int i=0;i<n;i++)
59     {
60         if(node[i].deg==1)
61             que.push(node[i]);
62     }
63     while(!que.empty())
64     {
65         Node u=que.front();
66         que.pop();
67         if(fa[u.sum]<0)
68             fa[u.cnt]=u.sum;
69         int j=fa[u.cnt];
70         node[j].deg--;
71         node[j].sum=change(u.cnt,node[j].sum);
72         if(node[j].deg==1)
73             que.push(node[j]);
74     }
75     for(int i=0;i<n;i++)
76     {
77         if(fa[i]!=-1)
78         {
79             printf("%d %d
",i,fa[i]);
80         }
81     }
82     return ;
83 }

View Code