victoria的舞会3(顶点数最小点基).cpp

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

//http://www.vijos.cn/Problem_Show.asp?id=1023
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define NMAX 220

vector< vector< int > > path;
vector< vector< int > > dag;
queue< int > SQ;
int n , scc, step;
int order[NMAX], order_pos, id[NMAX];
int order2[NMAX], order2_pos;
int vis[NMAX];
int out_degre[NMAX];

void dfs(int pos)
{
	int i,j,next,l,pre;

	vis[pos] = step ++;
	order[ order_pos ++ ] = pos;
	order2[ order2_pos ++ ] = pos;
	l = path[pos].size();
	for (i=0;i<l;i++) {
		next = path[pos][i];
		if (vis[next] == 0) {
			dfs(next);
		}
		else if (id[next] == 0) {//have a circle and belong to nothing
			while (vis[ order2[order2_pos -1] ] > vis[next]) {//back to begin of circle
				order2_pos --;
			}
		}
	}//for i
	if (order2[order2_pos -1] == pos) {//if pos back to begin of scc
		order2_pos --;
	}
	else {
		return ;
	}
	do {//record scc
		pre = order[order_pos -1];
		id[pre] = scc;
		order_pos --;
	} while(pre != pos);
	scc ++;
}

void Gabow()
{
	int i,j,l;
	//dfs in original graph
	memset(id, 0, sizeof(id));
	memset(vis, 0, sizeof(vis));
	scc = step = 1;
	order_pos = order2_pos = 0;
	for (i=1; i<=n ;i++) {
		if (vis[i] == 0) {
			dfs(i);
		}
	}
	scc --;
}

int top_sort()
{
	int i,j,k,l,m = 0;
	memset(out_degre,0,sizeof(out_degre));
	l = SQ.size();
	while (l --) {
		SQ.pop();
	}
	for (i=1;i<=n;i++) {
		int id1 = id[i];
		l = path[i].size();
		for (j=0;j<l;j++) {
			int id2 = id[ path[i][j] ];
			if (id1 != id2) {
				out_degre[id2] ++;
				dag[id1].push_back(id2);
			}
		}
	}
	for (i=1;i<=scc;i++) {
		if (out_degre[i] == 0) {
			SQ.push(i);
		}
	}
	while (!SQ.empty()) {
		int now = SQ.front();
		SQ.pop();
		l = dag[now].size();
		for (i=0;i<l;i++) {
			int next = dag[now][i];
			out_degre[next] --;
			if (out_degre[next] == 0) {
				SQ.push(next);
				m --;
			}
		}
	}
	return scc+m;
}

int main()
{
	int i,x;
	path.resize(NMAX);
	dag.resize(NMAX);
	while (scanf("%d",&n)==1) {
		for (i=0;i<=n;i++) {
			path[i].clear();
			dag[i].clear();
		}
		for (i=1;i<=n;i++) {
			while (scanf("%d",&x), x) {
				path[i].push_back(x);
			}
		}
		Gabow();
		printf("%d\n", top_sort());
	}
}