2011-06-07 17:28:49Morris
d808. 黑暗部落
http://zerojudge.tw/ShowProblem?problemid=d808
內容 ：
中土世界的南方有一塊神秘的陸地，被稱為「黑暗大陸」。在那裡並沒有精靈或矮人居住，但有些野人在黑暗大陸活動。努曼諾爾人在長途旅行中經過那裡，並發現野人們分為許多不同的部落。他們好奇，究竟這些野人總共組成了多少部落，並且也想知道，最大的那個部落有多少人。努曼諾爾人知道，一個野人只會屬於一個部落。他們開始詢問每個野人屬於什麼部落，然而，野人基於無法明白的原因，只願意告訴努曼諾爾人，他跟誰屬於相同的部落。現在，請從搜集到的資訊回答：總共有多少不同的部落，以及最大的部落有多少人。
輸入說明 ：
有多組測試資料，以EOF結尾。
每組測試資料的第一行是一個正整數N (N<=1000000) 表示黑暗大陸內共有多少野人。這些野人的編號從1~N。接下來有N個數字，其中的第k個數字x，表示第k個野人與編號x的野人屬於同一個部落。
輸出說明 ：
輸出兩個數字：部落的總數、最大部落的人數。
範例輸入 ：
54 5 1 3 242 1 4 3
範例輸出 ：
2 32 2
提示 ：
出處 ：
/**********************************************************************************/
/* Problem: d808 "黑暗部落" from */
/* Language: C */
/* Result: AC (118ms, 2781KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-02 22:25:13 */
/**********************************************************************************/
#include<stdio.h>
int Parent[1000001], Rank[1000001];
int a, Ans;
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), Ans--;
}
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, x, a;
while(scanf("%d", &N) == 1) {
MakeSet (N);
for(a = 1, Ans = N; a <= N; a++)
x = Input(), Union(a, x);
int max = 0;
for(a = 1; a <= N; a++)
if(Rank[a] > max) max = Rank[a];
printf("%d %d\n", Ans, max);
}
return 0;
}
上一篇：d807. 方方
下一篇：d809. 黑暗土地