Codeforces Round #285(Div. 1) A. Misha and Forest 토폴로지 정렬
2665 단어 codeforces
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.