2011-08-29 10:33:57Morris
d449. 垃圾信件
d449. 垃圾信件
內容 ：
即將上大學的小光莫名其妙收了一堆廣告信件，都在推銷一些大學必備的生活用品，但
是這些東西對現在的他完全沒有幫助，現在的小光只為了在大學找到「會寫程式」的夥
伴煩惱，不料，大學同學沒有一個人符合要求，更別說一起出題、解題了。
小光看著一信箱滿滿的垃圾信件瞬間燃起了怒火，他決定把這些信分類，開始砲轟回
去！但他已經被怒火蒙蔽了眼睛，在分類過程中不斷出差錯，想請你寫個程式來幫忙。
因為有些信件內容比較特別，小光決定特別把他們獨立出來砲轟，然而在小光發現別
封信件的內容更令人火大的時候，又會再次將這封信獨立出來，至於分去哪裡就要看
他的心情了。
現在操作有兩項：
1. 將信件 x, y 在同一類(與 x, y 同類的同時也會被分類在一起)
2. 信件 x 被獨立出來
分類結束後，如何砲轟自然是小光的事情，只要輸出全部分成幾類就可以了。
輸入說明
：
有多組測資，每組第一行有兩個數字 n, m (1 ≦ n ≦ 1,0000, 1 ≦ m ≦ 100,0000)
分別代表 信件編號 1~n, 以及 接下來有 m 的操作。
操作 1 x y 代表將信件編號 x y 分成同一類
操作 2 x 代表將信件編號 x 獨立
輸出說明
：
每組測資輸出總共分成幾類
範例輸入 ：
4 4 1 1 2 1 1 3 2 1 1 1 4
範例輸出 ：
2
提示
：
※ 待請 example 編輯題目
※ 待請白老鼠實驗
出處
：
(管理：morris1028)
作法 : 並查集 + 虛設點
代碼還很醜陋, 先放著了
/**********************************************************************************/
/* Problem: d449 "垃圾信件" from */
/* Language: C */
/* Result: AC (404ms, 6108KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-28 22:50:34 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Parent[1010001], Realpt[10001];
short Rank[1010001];
int Ans;
void Init(int n, int m) {
int a;
m = m > n ? m : n;
m += n;
for(a = 0; a <= m; a++)
Parent[a] = a, Rank[a] = 1;
for(a = 0; a <= n; a++)
Realpt[a] = a;
}
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--;
}
main() {
int n, m, op, vir, a, x, y, px;
while(scanf("%d %d", &n, &m) == 2) {
Init(n, m), Ans = n, vir = n+1;
for(a = 0; a < m; a++) {
scanf("%d", &op);
if(op == 1) {
scanf("%d %d", &x, &y);
Union(Realpt[x], Realpt[y]);
} else {
scanf("%d", &x);
px = FindSet(Realpt[x]);
if(Rank[px] > 1) {
Ans++;
Rank[px]--;
Realpt[x] = vir++;
}
}
}
printf("%d\n", Ans);
}
return 0;
}
上一篇：a194. 死亡 FLAG
下一篇：d650. 好多骰子