題意：給你一個圖，每條邊權值0或1，問每個點周圍最近的點有多少個？

思路：并查集找權值為0的點構成的連通塊。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<math.h>
 5 #include<algorithm>
 6 #define clc(a,b) memset(a,b,sizeof(a))
 7 using namespace std;
 8 int pre[100010],a[100010];//標記根節點
 9 int find(int x)//查找根節點
10 {
11     int r=x;
12     while(pre[r]!=r)//返回根節點r
13         r=pre[r];
14     int i=x,j;
15     while(i!=r)//路徑壓縮
16     {
17         j=pre[i];//在改變上級之前用臨時變量j記錄下他的值
18         pre[i]=r;//把上級改為根節點
19         i=j;
20     }
21     return r;
22 }
23 void join(int x,int y)//判斷x,y是否連通.如果已經連通,就不用管了;如果不連通,就把它們所在的連通分支合并起
24 {
25     int fx=find(x),fy=find(y);
26     if(fx!=fy) pre[fy]=fx;
27 }
28 int main()
29 {
30     //freopen("in.txt","r",stdin);
31     int t,n,x,y,z;
32     while(~scanf("%d",&t))
33     {
34         for(int i=0; i<t; i++)
35         {
36             clc(a,0);
37             scanf("%d",&n);
38             for(int i=1; i<=n; i++)
39             {
40                 pre[i]=i;
41             }
42             for(int i=1; i<n; i++)
43             {
44                 scanf("%d%d%d",&x,&y,&z);
45                 if(!z) join(x,y);
46             }
47             for(int i=1; i<=n; i++)
48             {
49                 a[find(i)]++;
50             }
51             long long ans=0;
52             for(int i=1; i<=n; i++)
53             {
54                 int p=a[find(i)];
55                 if(p) ans^=p;
56                 else ans^=1;
57             }
58             printf("%I64d\n",ans);
59         }
60     }
61     return 0;
62 }

View Code

?

轉載于:https://www.cnblogs.com/ITUPC/p/5095308.html

總結

以上是生活随笔為你收集整理的BestCoder Round #68 (div.2) 1002 tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。