going from u to v or from v to u(强连通分量).cpp

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

#include <cstdio>
#include <string>
#include <queue>
#include <vector>
using namespace std;
#define NMAX 1100

int t,n,m;
int step,scc;
int or[NMAX], por, or2[NMAX], por2;
vector< vector<int> > path;
vector< vector<int> > dag;
queue< int > SQ;
int degre[NMAX];
int vis[NMAX], id[NMAX];

void dfs(int pos)
{
	int i,pre;
	vis[pos] = step ++;
	or[por ++] = pos;
	or2[por2 ++] = pos;
	int l = path[pos].size();
	for (i=0;i<l;i++) {
		int next = path[pos][i];
		if (vis[next] == 0) {
			dfs(next);
		}
		else if (id[next] == 0) {
			while ( vis[ or2[por2 -1] ] > vis[next]) {
				por2 --;
			}
		}
	}
	if (or2[por2 -1] == pos) {
		por2 --;
	}
	else {
		return ;
	}
	do {
		pre = or[por -1];
		id[pre] = scc;
		por --;
	} while (pre != pos);
	scc ++;
}

void Gabow()
{
	int i,j;
	memset(vis,0,sizeof(vis));
	memset(id,0,sizeof(id));
	step = scc = 1;
	or[0] = or2[0] = INT_MIN;
	por = por2 = 1;
	for (i=1;i<=n;i++) {
		if (vis[i] == 0) {
			dfs(i);
		}
	}
	scc --;
}

bool top_sort()
{
	int i,now,next,l;
	while (!SQ.empty()) {
		now = SQ.front();
		SQ.pop();
		if (!SQ.empty()) {
			return false;
		}
		degre[now] = -1;
		for (i=dag[now].size()-1; i>=0 ;i--) {
			next = dag[now][i];
			degre[next] --;
			if (degre[next] == 0) {
				SQ.push(next);
			}
		}
	}
	return true;
}

int main()
{
	int i,j;
	scanf("%d",&t);
	while (t --) {
		scanf("%d %d",&n,&m);
		path.resize(n+10);
		for (i=0;i<=n;i++) {
			path[i].clear();
		}
		for (i=0;i<m;i++) {
			int x,y;
			scanf("%d %d",&x,&y);
			path[x].push_back(y);
		}
		Gabow();
		dag.resize(scc+10);
		for (i=0;i<=scc;i++) {
			dag[i].clear();
		}
		memset(degre,0,sizeof(degre));
		for (i=1;i<=n;i++) {
			int id1 = id[i];
			for (j=path[i].size()-1; j>=0 ;j--) {
				int id2 = id[ path[i][j] ];
				if (id1 != id2) {
					dag[id1].push_back(id2);
					degre[id2] ++;
				}
			}
		}
		while (!SQ.empty()) {
			SQ.pop();
		}
		for (i=1;i<=scc;i++) {
			if (degre[i] == 0) {
				SQ.push(i);
			}
		}
		bool ans = top_sort();
		puts(ans ? "Yes" : "No");
	}
}