hdu 5606 tree（并查集）

发布时间：2020-12-13 21:10:24 所属栏目：PHP教程来源：网络整理

导读：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5606 tree Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1183Accepted Submission(s): 527 Problem Description There is a tree(the tree

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5606

tree

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1183 Accepted Submission(s): 527

Problem Description

There is a tree(the tree is a connected graph which contains

n points and

n?1 edges),the points are labeled from 1 to

n,which edge has a weight from 0 to 1,for every point

i∈[1,n],you should find the number of the points which are closest to it,the clostest points can contain

i itself.

Input

the first line contains a number T,means T test cases.

for each test case,the first line is a nubmer

n,means the number of the points,next n⑴ lines,each line contains three numbers

u,v,w,which shows an edge and its weight.

T≤50,n≤105,u,v∈[1,n],w∈[0,1]

Output

for each test case,you need to print the answer to each point.

in consideration of the large output,imagine

ansi is the answer to point

i,you only need to output,

ans1 xor ans2 xor ans3.. ansn.

Sample Input

Sample Output

1

in the sample.

$ans_1=2$

$ans_2=2$

$ans_3=1$

$2~xor~2~xor~1=1$,so you need to output 1.

Source

BestCoder Round #68 (div.2)

题目大意：

有1个树（n个点，n⑴条边的连通图），有1个树(n个点,n?1条边的联通图),点标号从1~n,树的边权是0或1.求离每一个点最近的点个数(包括自己).

解题思路：1开始想着只要判断ｗ为０就行了，ｗ为０的时候直接给连通的这两个点都加１处理，最后再加上本身这个点就是答案了！！但是这个是毛病的！！！ｗｒｏｎｇ　ａｎｓｗｅｒ！！！

下面解释1下：举1个例子：

１

　４

　１　２　０

　２　３　０

　１　４　０如果是这组数据的话，我们需要怎样处理呢？如果依照上陈述法计算的话，对１这个点，与其最近的点只有两个，但实际上有3个！！所以就不可以采取上述方法，所以采取并查集的方法，只要ｗ＝０就给连通起来。在计算个数便可。

详见代码。

#include <iostream> #include <cstdio> #include <cstring> using namespace std; int num[100010]; int fa[100010]; int Find(int x) { if (x!=fa[x]) { return fa[x]=Find(fa[x]); } return x; } void Unit(int x,int y) { x=Find(x); y=Find(y); if (x!=y) { fa[x]=y; num[y]+=num[x];//把两个点连通，同时也要加上子节点在这之前就已连通的点 } } int main() { int t; scanf("%d",&t); while (t--) { int n; scanf("%d",&n); for (int i=1; i<=n; i++) fa[i]=i,num[i]=1; int u,v,w; int s=0; for (int i=1; i<=n⑴; i++) { scanf("%d%d%d",&u,&v,&w); if (w==0) { Unit(u,v); } } for (int i=1; i<=n; i++) { if (fa[i]==i&&num[i]%2==1) s=num[i]^s; } printf ("%dn",s); } return 0; }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!