2011-08-26 07:54:34Morris
d429. 第一題: 社團分組 (club)
d429. 第一題: 社團分組 (club)
內容 ：
有一個社團，其中的社員間並不完全認識，社長想將社員分組以方便聯繫消
息。該社團聯繫消息的方式是社長只電話通知各組中任一個社員，當一個社員
知道消息後要向同一組中其他認識的社員以電話通知。而社長分組的依據是不
會因為一組中只有一個社員的電話故障，而造成同組中其他人沒有獲知消息。
給定社員間認識的關係，請寫一個程式來找出最少的組別可以達到上述效果。
輸入說明
：
(技術限制：社員編號從正整數1依序表示，例如有三個社員，則以社員1，社
員2，社員3來表示。)
第一行為一正整數N，1 < N < 25，表示社員數目。第二行起每一行表示互相認
識的社員配對，以0表示結束。兩個社員編號間以空白分開，例如1 3 表示社
員1認識社員3，亦表示社員3認識社員1，且出現編號沒有順序性。
輸出說明
：
顯示最少分組數目。
範例輸入 ：
6 1 3 3 4 5 1 2 6 4 5 6 3 5 3 0
範例輸出 ：
2
提示
：
出處
：
92
(管理：nanj0178)
作法 : 一次 DFS, 標記搜尋的深度, 以及可以返回的最小深度,
藉此找到所有關節點, 然後關節點用 Greedy 去做處理
測資有點弱了, 所以我不曉得, 這樣的做法, 能不能包含所有情況,
就以目前是可以的
作法 : 一次 DFS, 標記搜尋的深度, 以及可以返回的最小深度,
藉此找到所有關節點, 然後關節點用 Greedy 去做處理
測資有點弱了, 所以我不曉得, 這樣的做法, 能不能包含所有情況,
就以目前是可以的
/**********************************************************************************/
/* Problem: d429 "第一題: 社團分組 (club)" from 92 */
/* Language: C */
/* Result: AC (1ms, 230KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-25 23:54:30 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
#define oo 100000
int map[30][30], used[30], back[30], joint[30], chose[30];
int n, find, Ans;
int min(int x, int y) {
return x < y ? x : y;
}
int DFS(int now, int last, int depth) {
int a, back_depth = depth-1, t;
back[now] = depth, find++;
for(a = 0; a <= n; a++) {
if(map[now][a]) {
if(used[a]) {
back_depth = min(back_depth, back[a]);
} else {
used[a] = 1;
t = DFS(a, now, depth+1);
back_depth = min(back_depth, t);
}
}
}
if(back_depth == depth-1) {
for(a = 0; a <= n; a++)
if(map[now][a] && joint[a] == 1 && chose[a] == 1)
break;
if(a == n+1) {Ans++;chose[now] = 1;}
joint[now] = 1;
}
return back_depth;
}
main() {
int x, y;
while(scanf("%d", &n) == 1) {
memset(map, 0, sizeof(map));
memset(used, 0, sizeof(used));
memset(chose, 0, sizeof(chose));
memset(joint, 0, sizeof(joint));
while(scanf("%d", &x) == 1 && x) {
scanf("%d", &y);
map[x][y] = 1, map[y][x] = 1;
}
Ans = 0, find = 0, used[1] = 1, DFS(1, 0, 0);
printf("%d\n", Ans+(n-find));
}
return 0;
}