2011-06-10 19:40:16Morris
d831. 畢業旅行
http://zerojudge.tw/ShowProblem?problemid=d831
內容 ：
多年來友情的羈絆，終於將在這畢業的季節開花結果。
這幾天，班上同學們無時無刻都熱烈討論著畢業旅行的地點。
小明說，如果要去六福村，可以順便去小人國；
小美說，如果去了恆春的話，墾丁就在幾十公里外了，一定也要去玩；
小華表示，小鬼湖跟大鬼湖好像很近，似乎都是很有趣的地方。
身為班長，聽到同學這麼多「去了哪裡也可以去哪裡」的資訊後，
你決定要為班上的同學們，找到一個能玩最多景點的畢業旅行。
輸入說明
：
有多組測試資料，以 EOF 結束。
每組測試資料的第一行有兩個正整數 n (n<=1000000) 和 m (m<=100000)，
表示景點有 n 個，編號為 0 ~ n-1。
接下來有 m 行，每行有兩個整數 a 和 b (0<=a,b<n)，
表示去了 a 的同時也可以去 b（反過來也一樣）。
輸出說明
：
輸出一個數字，表示畢業旅行最多可以玩的景點數量。
範例輸入 ：
6 4 0 1 2 3 1 3 5 4 1000000 0 1000000 1 0 999999
範例輸出 ：
4 1 2
提示
：
出處
：
/**********************************************************************************/
/* Problem: d831 "畢業旅行" from */
/* Language: C */
/* Result: AC (20ms, 3389KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-04 19:46:34 */
/**********************************************************************************/
#include<stdio.h>
int Parent[1000001], Rank[1000001];
int a;
void MakeSet(int N) {
for(a = 0; a <= N; a++)
Parent[a] = a, Rank[a] = 1;
}
int FindSet(int x) {
if(x != Parent[x])
Parent[x] = FindSet(Parent[x]);
return Parent[x];
}
void Link(int x, int y) {
if(Rank[x] > Rank[y])
Parent[y] = x, Rank[x] += Rank[y];
else
Parent[x] = y, Rank[y] += Rank[x];
}
void Union(int x, int y) {
x = FindSet(x), y = FindSet(y);
if(x != y)
Link(x, y);
}
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n' || cha == EOF) break;
if(cha == EOF) return -1;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
main() {
int N, M, x, y, a;
while(scanf("%d %d", &N, &M) == 2) {
MakeSet (N);
for(a = 0; a < M; a++)
x = Input(), y = Input(), Union(x, y);
int max = 0;
for(a = 0; a < N; a++)
if(Rank[a] > max) max = Rank[a];
printf("%d\n", max);
}
return 0;
}
上一篇：d806. 水火不容
下一篇：d832. 遊樂場