首页 > 代码库 > Codeforces Round #285 Div1 A and Div2 C
Codeforces Round #285 Div1 A and Div2 C
Codeforces Round #285 Div1 A and Div2 C
Problem
给一个图G，保证G是一个森林（坑！）。图G含有N个点，给出每个点的两个属性：度数(degree)、异或和(sum)。度数表示该点与多少个点相连，异或和表示与其相连的点的编号的异或和（点编号从0开始，若度数为0则异或和为0）。要求求出原图，输出边的个数和每条边两端的顶点。
Limits
Time Limit(ms): 1000
Memory Limit(MB): 256
N: [1, 2^16]
degree: [0, N-1]
Solution
由于G是森林，G的每一个连通图一定是一棵树，树一定无环无回路，可拓扑排序。按照拓扑排序的方法，不断维护点的度数和异或和，适当入队列，即可解。
More
起初将入度为1的结点入队列，每次从队列中取出点（不妨假设为now），now的度数一定不超过1，若为1，那么其异或和(sum)一定是与其相连的点的编号（不妨假设为to）；将to的异或和sum与now进行运算（sum^=now），再将to的度数减一，若减一后to的度数变为1，则入队列。如此循环，直到队列为空。每次的now和to则为一条边的两端顶点。
Complexity
Time Complexity: O(N)
Memory Complexity: O(N)
Source
Codeforces Round #285 Div1 A and Div2 C
Code
Codeforces Round #285 Div1 A and Div2 C From My Github
Codeforces Round #285 Div1 A and Div2 C
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。