首页 > 代码库 > CodeForces Round #285 Div.2
CodeForces Round #285 Div.2
C.Misha and Forest (图论 BFS)
比赛进行了一半才想起来有场CF没打，=_=||
前两道题快速切掉，C题一直卡没什么好的思路
憋了几天，忍不住偷偷瞄了一下别人AC的代码，发现我题没看清题目，题中说了给出的图是森林。
于是切入点找到了！
题意：
一个由n个节点构成的森林，编号从0到n-1，给出每个节点的 度数 和 相邻节点编号的异或和，输出图中的边数和所有邻接节点的编号。
分析：
因为是森林，所以图中的叶子节点就是突破口。叶子节点最明显的特征就是：
- 度数为1
- 它相邻节点编号的异或和 就是 它唯一的邻居本身的编号
这样就找到一条边。
所以我们就可以像剥洋葱一样，把外面的叶子节点一层一层的剥去。
可以用一个队列来维护，开始将所有的叶子节点入队，然后逐个向内拓展。如果将这个叶子节点去掉后又出现新的叶子节点，则将新节点入队，直到队列为空。
1 #include <cstdio> 2 3 const int maxn = (1 << 16) + 10; 4 5 int degree[maxn], xorsum[maxn]; 6 int edge[maxn][2], cnt = 0; 7 int Q[maxn], head = 0, tail = 0; 8 int main() 9 {10 int n;11 scanf("%d", &n);12 for(int i = 0; i < n; i++)13 {14 scanf("%d%d", °ree[i], &xorsum[i]);15 if(degree[i] == 1) Q[tail++] = i;16 }17 18 while(head < tail)19 {20 int t = Q[head++];21 if(degree[t] == 0) continue;22 degree[t] = 0;23 int neighbor = xorsum[t];24 edge[cnt][0] = t; edge[cnt++][1] = neighbor;25 degree[neighbor]--;26 xorsum[neighbor] ^= t;27 if(degree[neighbor] == 1) Q[tail++] = neighbor;28 }29 30 printf("%d\n", cnt);31 for(int i = 0; i < cnt; ++i) printf("%d %d\n", edge[i][0], edge[i][1]);32 33 return 0;34 }
CodeForces Round #285 Div.2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。