大家快來(lái)A水題

Time Limit: 1000MS Memory limit: 65536K

題目描寫(xiě)敘述

(1<= N <=2000)(1<= M <= N*(N-1)/2)多組輸入。每組第一行輸入N。M。接下來(lái)M行每行。每行兩個(gè)整數(shù)u,v代表島u與v之間有一條路。

輸出

<span 宋體;="" font-size:="" 14px;="" text-align:="" justify;\"="" style="padding: 0px; margin: 0px;">每組數(shù)據(jù)輸出一個(gè)整數(shù)，代表部落數(shù)。

演示樣例輸入

3 1
1 2
3 2
1 2
1 3

演示樣例輸出

2
1

#include <bits/stdc++.h>using namespace std;int f[21000];
int n,m;int Find(int x)
{int r = x;while(r != f[r])r = f[r];return r;
}//int Find(int x)
//{
//    return x == f[x] ?

x : Find(f[x]); //} void Link(int a, int b) { int fx = Find(a); int fy = Find(b); if(fx != fy) f[fx] = fy; } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n; i++) f[i] = i; int a, b; while(m--) { cin>>a>>b; Link(a, b); } int ant = 0; for(int i=1; i<=n; i++) { if(f[i] == i) ant++; } printf("%d\n",ant); } return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/liguangsunls/p/7110566.html

總結(jié)

以上是生活随笔為你收集整理的sdut 2805（最小生成树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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