【并查集】Tree

tree

Problem Description
There is a tree(the tree is a connected graph which contains points and edges),the points are labeled from 1 to ,which edge has a weight from 0 to 1,for every point ,you should find the number of the points which are closest to it,the clostest points can contain itself.


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

for each test case,the first line is a nubmer ,means the number of the points,next n-1 lines,each line contains three numbers ,which shows an edge and its weight.

 

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

in consideration of the large output,imagine is the answer to point ,you only need to output,.
Sample Input
1 3 1 2 0 2 3 1
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)

#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-1; 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;
}

 

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

9 + 7 =