樹結(jié)構(gòu)練習(xí)——判斷給定森林中有多少棵樹

Time Limit: 1000MS Memory limit: 65536K

題目描述

眾人皆知，在編程領(lǐng)域中，C++是一門非常重要的語言，不僅僅因為其強(qiáng)大的功能，還因為它是很多其他面向?qū)ο笳Z言的祖先和典范。不過這世上幾乎沒什么東西是完美的，C++也不例外，多繼承結(jié)構(gòu)在帶來強(qiáng)大功能的同時也給軟件設(shè)計和維護(hù)帶來了很多困難。為此，在java語言中，只允許單繼承結(jié)構(gòu)，并采用接口來模擬多繼承。KK最近獲得了一份java編寫的迷你游戲的源代碼，他對這份代碼非常感興趣。這份java代碼是由n個類組成的（本題不考慮接口），現(xiàn)在，他想要知道這份代碼中有多少個類沒有直接基類。n個類分別用數(shù)字1..n表示。

輸入

輸入數(shù)據(jù)包含多組，每組數(shù)據(jù)格式如下。 第一行包含兩個整數(shù)n,m，表示該份代碼中的n個類和m個單繼承關(guān)系。 后面m行，每行兩個整數(shù)a b，表示a是b的直接基類。

輸出

對于每組輸入，輸出該組數(shù)據(jù)中有多少個類沒有直接基類。每組輸出占一行。

示例輸入

2 1 1 2 2 0

示例輸出

1 2



并查集 View Code 1 #include<stdio.h> 2 int a[10005]; 3 int find(int x) 4 { 5 while(x != a[x]) 6 x = a[x]; 7 return x; 8 } 9 void merge(int x, int y) 10 { 11 x = find(x); 12 y = find(y); 13 if(a[x] != y) 14 a[x] = y; 15 } 16 int main() 17 { 18 int n, i, m, x, y, count; 19 while(~scanf("%d%d",&n,&m)) 20 { 21 for(i = 1; i <= n; i++) 22 { 23 a[i] = i; 24 } 25 for(i = 0; i < m; i++) 26 { 27 scanf("%d%d",&x, &y); 28 merge(x,y); 29 } 30 count = 0; 31 for(i = 1; i <= n; i++) 32 { 33 if(i == a[i]) 34 count++; 35 } 36 printf("%d\n",count); 37 } 38 return 0; 39 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wanglin2011/archive/2012/07/26/2610196.html

總結(jié)

以上是生活随笔為你收集整理的sdut 2129树结构练习——判断给定森林中有多少棵树（并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。