network(割点).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

const int MAX = 110;
int n;
bool path[MAX][MAX];
int vis[MAX], low[MAX];
vector<int> cutpoint;
vector< pair<int,int> > bridge;

#define mclear(x) memset((x), 0, sizeof((x)))

void dfs(int pos, int deep, int father) {
	int i, total = 0;
	bool cut = false;
	vis[pos] = deep;
	low[pos] = deep;
	for(i=1;i<=n;i++) {
		if(path[pos][i]) {
			if(vis[i] == 0) {
				dfs(i, deep+1, pos);
				total ++;
				low[pos] = min(low[i], low[pos]);
				if((deep == 1 && total > 1) || 
					(deep != 1 && low[i] >= vis[pos])) cut = true;
				if(low[i] > vis[pos]) bridge.push_back(pair<int,int>(pos,i));
			}
			else if(i != father) {
				low[pos] = min(vis[i], low[pos]);
			}
		}
	}
	if(cut) cutpoint.push_back(pos);
}

void find_cut() {
	int i;
	mclear(vis); mclear(low);
	cutpoint.clear(); bridge.clear();
	for(i=1;i<=n;i++) {
		if(vis[i] == 0) {
			dfs(i, 1, i);
		}
	}
}

int main() {
	char line[1100];
	while(scanf("%d", &n), n) {
		getchar();
		memset(path, 0, sizeof(path));
		while(gets(line)) {
			if(line[0] == '0' && line[1] == 0) break;
			istringstream sin(line);
			int s,t;
			sin >> s;
			while(sin >> t) path[s][t] = path[t][s] = true;
		}
		find_cut();
		printf("%d\n", cutpoint.size());
	}
}