Codeforces #285 C Misha and Forest 队列维护 解题报告

题目大意为一个森林,对于每个节点记录它的度数degree和与它连接的点的异或和Sv。现在给出每个点的degree和Sv,求这个图有多少条边,并写出每条边的顶点。

分析:

首先从异或和出发,加入x^y^z = a,那么左右都异或x的话,(x^x)^y^z = a^x,即y^z = a^x,同理z = a^x^y。

其次由于是森林,肯定有叶子节点,找出这些叶子节点,他们的degree均为1,且Sv为父节点的编号,每遍历一个叶子节点,将其父节点度数-1,Sv异或叶子节点编号,直到找到最后一个节点即可。

最后,需要用队列维护,不然会T。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
struct node{
int degree,s,i;
int vis;
void output(){
cout<<i<<" "<<degree<<" "<<s<<endl;
}
}v[70000];
typedef pair<int, int> PII;
vector<PII> edge;
vector<PII>::iterator it;
queue <int> q;
int main()
{
freopen("in.txt","r",stdin);
int n;
scanf("%d",&n);
int cnt = 0;
for(int i = 0 ; i < n;i++)
{
scanf("%d%d",&v[i].degree,&v[i].s);
if(v[i].degree == 1)
q.push(i);
}
while(!q.empty())
{
int i = q.front();
q.pop();
if(v[i].degree == 1)
{
int fa = v[i].s;
v[fa].s ^= i;
v[fa].degree --;
edge.push_back(make_pair(i,fa));
if(v[fa].degree == 1)
q.push(fa);
}
}
cout<<edge.size()<<endl;
for(it = edge.begin();it!=edge.end();it++)
{
PII pb = *it;
cout<<pb.first<<" "<<pb.second<<endl;
}
}