1789.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 1789 on 2006-09-14 at 20:37:56 */
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 10240;
 
class Graph {
private:
//public:
	vector<int> nei[N];
	int n, part, cnt, dfn[N], low[N];
	void dfs(int, int);
public:
	bool make();
	int connection();
};
bool Graph::make() {
	int i, c; scanf("%d %d", &n, &c);
	if(n == 0) return false;
	for(i = 0; i < n; i++) nei[i].clear();
	for(i = 0; i < c; i++) {
		int a, b; scanf("%d %d", &a, &b);
		nei[a].push_back(b); nei[b].push_back(a);
	}
	return true;
}
int Graph::connection() {
	int i, scnt = cnt = 0;
	part = -1; memset(dfn, -1, sizeof(dfn));
	for(i = 0; i < n; i++)
		if(dfn[i] == -1) { scnt++; dfs(i, -1); }
	return part+scnt;
}
void Graph::dfs(int o, int p) {
	int i, kn = 0;
	low[o] = dfn[o] = cnt++;
	for(i = 0; i < nei[o].size(); i++) {
		int nto = nei[o][i];
		if(dfn[nto] == -1) {
			dfs(nto, o);
			if(low[nto] >= dfn[o]) kn++;
		}
		if(dfn[nto] > dfn[o]) low[o] = min(low[o], low[nto]);
		else low[o] = min(low[o], dfn[nto]);
	}
	if(p == -1) kn--;
	part = max(part, kn);
}
 
int main()
{
	Graph g;
 
	while(g.make()) printf("%d\n", g.connection());
	
	return 0;
}