Codeforces Round #285(Div. 1) A. Misha and Forest 토폴로지 정렬

2665 단어 codeforces
A. Misha and Forest
time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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.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
32 31 01 0
Output
21 02 0
Input
21 11 0
Output
10 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".
제목의 뜻
숲을 하나 주고 각 점 주위에 몇 점, 그리고 이 점과 주위 점 번호의 이화합을 주고 이 가장자리를 출력하라.
문제풀이
음, 이것은 토폴로지 서열입니다. 쉽게 똑같이 알아볼 수 없습니다. 우선, 가장자리의 개수는 바로 인접점수와/2입니다. 그리고 입도가 1인 점을 대기열에 넣고 그와 인접한 점의 좌표입니다. 바로 그 이차값입니다. 그리고 토폴로지 서열을 한 번 뛰면 바로 코드를 자세히 보십시오.
코드
struct node
{
	int id;
	int x;
	int y;
};
node kiss[maxn];
int main()
{
	int n;
	cin>>n;
	int ans=0;
	REP(i,n)
	{
		kiss[i].id=i;
		cin>>kiss[i].x;
		cin>>kiss[i].y;
		ans+=kiss[i].x;
	}
	queue<node> q;
	for(int i=0;i<n;i++)
	{
		if(kiss[i].x==1)
		{
			q.push(kiss[i]);
		}
	}
	cout<<ans/2<<endl;
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		if(kiss[now.id].x!=1)
			continue;
		cout<<now.id<<" "<<now.y<<endl;
		kiss[now.id].x--;
		kiss[now.y].x--;
		kiss[now.y].y^=now.id;
		if(kiss[now.y].x==1)
			q.push(kiss[now.y]);
	}
	return 0;
}

좋은 웹페이지 즐겨찾기