hdu 5606 tree（并查集）
來源：程序員人生 發布時間：2016-07-04 16:07:20 閱讀次數：2433次
題目鏈接：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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
