HDU3594 Cactus 强连通 判断一条边是否只在一个环内

1：强连通图

2：图中每条边只处于一个环内

怎么样判断一个边只在一个环内呢？其实在没有找到一个环之前的时候，有一个DFS的过程，在这个过程中每走到一个点，我们就记录一下它是有哪一个点走下来的 也就是这个点的上一层的点，等到我们找到环的时候，我们马上返回去查找，查找那个点是 out了两次以上，那么肯定有边处于两个或者两个以上环内，就不符合了

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-7

#define inf 0xfffffff
//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;



typedef struct Node{
	int from,to;
	int nex;
	int value;
};

Node edge[20000 * 500];

int head[20000 + 10],low[20000 + 10],dfn[20000 + 10],id[20000 + 10],Stack[20000 + 10],out[20000 + 10];
bool vis[20000 + 10];
int father[20000 + 10];

int vis_num,scc_num,tot,stack_num,tot2;
bool flag;

int min(int a,int b) {
	if(a<b)
		return a;
	else
		return b;
}

void clear() {
	memset(head,-1,sizeof(head));
	memset(dfn,-1,sizeof(dfn));
	memset(vis,false,sizeof(vis));
	memset(low,0,sizeof(low));
	memset(Stack,0,sizeof(Stack));
	memset(out,0,sizeof(out));
	vis_num = 0;
	scc_num = 0;
	tot = 0;
	stack_num = 0;
	flag = false;
}

void addedge(int u,int v) {
	edge[tot].from = u;
	edge[tot].to = v;
	edge[tot].nex = head[u];
	head[u] = tot++;
}

void find(int u,int v) {//这里返回去查找
	while(father[v] != u) {
		out[v]++;
		if(out[v] > 1) {
			flag = true;
			return ;
		}
		v = father[v];
	}
}

void tarjan(int v) {
	dfn[v] = low[v] = ++vis_num;
	vis[v] = true;
	Stack[stack_num++] = v;
	for(int i=head[v];i!=-1;i=edge[i].nex) {
		int u = edge[i].to;
		if(dfn[u] == -1) {
			father[u] = v;//记录上一个点是哪个点
			tarjan(u);
			low[v] = min(low[u],low[v]);
		}
		else if(vis[u]) {
			low[v] = min(dfn[u],low[v]);
			find(u,v);//遇到环了 马上返回去进行查找
		}
	}
	int tmp;
	if(low[v] == dfn[v]) {
		scc_num++;
		do {
			tmp = Stack[--stack_num];
			id[tmp] = scc_num;
			vis[tmp] = false;
		}while(tmp != v);
	}
	if(scc_num > 1) {
		flag = true;
		return;
	}
}


void cal(int n) {
	for(int i=1;i<=n;i++) {
		if(dfn[i] == -1)
			tarjan(i);
		if(flag)
			break;
	}
}

int main() {
	int t,n;
	scanf("%d",&t);
	while(t--) {
		clear();
		scanf("%d",&n);
		int a,b;
		while(true) {
			scanf("%d %d",&a,&b);
			if(a == 0 && b == 0)
				break;
			addedge(a + 1,b + 1);
		}
		cal(n);
		if(flag)
			puts("NO");
		else
			puts("YES");
	}
	return EXIT_SUCCESS;
}

HDU3594 Cactus 强连通 判断一条边是否只在一个环内

原文：http://blog.csdn.net/yitiaodacaidog/article/details/18740589