POJ 1144 Network(割点数)

テーマ接続:Network
解題の構想:図の中に点の数量を切ることがないことを求めて、直接テンプレートを使って、入力する時注意して、ここの入力する量は不定です

#include<stdio.h>
#include<string.h>
#define MAX 110

int map[MAX][MAX], v[MAX], num[MAX], low[MAX], c[MAX], n, ans;
 
 void cut(int cur, int father, int depth){
 	int i, children = 0;
 	v[cur] = 1;
 	num[cur] = low[cur] = depth;
 	for(i = 1; i <= n; i++){
	 	if(map[cur][i]){
	 		if(v[i] == 1 && i != father){
		 		if(low[cur] > num[i]){
		 			low[cur] = num[i];
		 		}
		 	}
		 	if(!v[i]){
	 			cut(i, cur, depth + 1);
	 			children++;
	 			if(low[i] < low[cur]){
			 		low[cur] = low[i];
			 	}
			 	if((father == -1 && children > 1) || (father != -1 && low[i] >= num[cur])){
	 				c[cur] = 1;
	 			}
	 		}
	 	}
	 }
	 v[cur] = 2;
 }
 
 int main(){
 	int i, j, k, tem, index;
 	char line[210];
 	while(scanf("%d", &n) && n){
 		getchar();
 		memset(v, 0, sizeof(v));
 		memset(map, 0, sizeof(map));
 		memset(num, 0, sizeof(num));
 		memset(low, 0, sizeof(low));
 		memset(c, 0, sizeof(c));
 		ans = 0;
	 	while(scanf("%d",&tem) && tem){ 
           while(getchar() != '
'){ 
             scanf("%d",&index); 
             map[index][tem] = map[tem][index] = 1; 
           } 
       }
	 	cut(1, -1, 1);
	 	for(i = 1; i <= n; i++){
	 		if(c[i]){
		 		ans++;
		 	}
	 	}
	 	printf("%d
", ans);
	 }
	 return 0;
 }