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 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.
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.
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 "
森林是没有环的,而且没有重边, 既然如此,就一定有度为1的点,对于度为1 的点,sv就是与其相邻的点,所以我们我们可以用一个队列来维护这些度为1的点,只要找到这些点,边就可以输出来
/*************************************************************************
> File Name: cf285c.cpp
> Author: ALex
> Mail: 405045132@qq.com
> Created Time: 2015年01月12日 星期一 17时41分31秒
************************************************************************/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 70000;
int deg[N];
int s[N];
queue <int> qu;
int main()
{
int n;
while (~scanf("%d", &n))
{
int sum = 0;
while (!qu.empty())
{
qu.pop();
}
for (int i = 0; i < n; ++i)
{
scanf("%d%d", °[i], &s[i]);
sum += deg[i];
if (deg[i] == 1)
{
qu.push(i);
}
}
printf("%d\n", sum / 2);
while (!qu.empty())
{
int u = qu.front();
qu.pop();
if (deg[u] == 0)
{
continue;
}
int v = s[u];
printf("%d %d\n", u, v);
deg[v]--;
s[v] ^= u;
if (deg[v] == 1)
{
qu.push(v);
}
}
}
return 0;
}