1 second
256 megabytes
standard input
standard output
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 ofn vertices. For each vertex
v from 0 to
n - 1 he wrote down two integers, degreev andsv, were the first integer is the number
of vertices adjacent to vertexv, and the second integer is the XOR sum of the numbers of vertices adjacent tov (if there were no adjacent vertices, he wrote down0).
Next day Misha couldn't remember what graph he initially had. Misha has valuesdegreev andsv 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.
The first line contains integer n (1 ≤ n ≤ 216), the number of vertices in the graph.
The i-th of the next lines contains numbersdegreei andsi
(0 ≤ degreei ≤ n - 1,0 ≤ si < 216), separated by a space.
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.
3 2 3 1 0 1 0
2 1 0 2 0
2 1 1 1 0
1 0 1
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".
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int degree[1<<16],s[1<<16];
for(int i=0;i<n;i++)
cin>>degree[i]>>s[i];
queue<int>qq;
for(int i=0;i<n;i++)
if(degree[i]==1)//如果只有一个点与它相连，那么这个点的情况已知
qq.push(i);//把它们加入队列中，用来推出其它情况
vector<pair<int,int> >ans;
while(qq.size())
{
int a=qq.front();
qq.pop();
if(degree[a]==0)//防止作死
continue;
int b=s[a];//因为就一个点跟a相连，所以，s[a]的值就是那个点
ans.push_back(make_pair(a,b));
degree[a]--;
degree[b]--;
s[b]^=a;//用掉了一个点
if(degree[b]==1)//同之前所说
qq.push(b);
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++)
cout<<ans[i].first<<" "<<ans[i].second<<endl;
}