hdu 5606 tree（并查集）
来源：程序员人生 发布时间：2016-07-04 16:07:20 阅读次数：2095次
题目链接：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 ("%d\n",s);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
