POJ2186 Popular Cows 【强连通分量】+【Kosaraju】+【Tarjan】

2017年04月23日 9点热度 0人点赞 0条评论
/*
Popular Cows ( POJ No.2186)
每头牛都想成为牛群中的红人。给定 N 头牛的牛群和 M 个有序对(A, B)。 (A, B)表示牛 A 认
为牛 B 是红人。该关系具有传递性,所以如果牛 A 认为牛 B 是红人,牛 B 认为牛 C 是红人,
那么牛 A 也认为牛 C 是红人。不过,给定的有序对中可能包含(A, B)和(B, C),但不包含(A, C)。
求被其他所有牛认为是红人的牛的总数。
限制条件
 1 ≤ N ≤ 10000
 1 ≤ M ≤ 50000
 1 ≤ A, B ≤ N
 
Sample Input
3 3
1 2
2 1
2 3
Sample Output
1
次题为典型的求强连通分量的题目,将强连通分量缩点并得到DAG,
求的出度为0的强连通分量的点的个数就是答案
*/ 
//Kosaraju算法,异常巧妙
#include
#include
#include
using namespace std;
const int maxn=10000+10,maxm=50000+10;
int n,m,scc;
int stack[maxn],top;
int head1[maxn],head2[maxn];
struct node{
	int to,next;
};
node edge1[maxm],edge2[maxm];//正向边与反向边
bool vis[maxn];
int num[maxn];//强连通分量点个数 
void dfs1(int u){
	int v;
	for(int i=head1[u];i!=-1;i=edge1[i].next){
		v=edge1[i].to;
		if(!vis[v]){
			vis[v]=1;
			dfs1(v);
		}
	}
	stack[top++]=u;
}
void dfs2(int u){
	int v;
	num[scc]++;
	for(int i=head2[u];i!=-1;i=edge2[i].next){
		v=edge2[i].to;
		if(!vis[v]){
			vis[v]=1;
			dfs2(v);
		}
	}
}
int main(int argc,char* argv[]){
	int u,v;
	while(~scanf("%d%d",&n,&m)){
		//init
		scc=top=0;
		memset(head1,-1,sizeof(head1));
		memset(head2,-1,sizeof(head2));
	
		for(int i=0;i=0;top--)
		if(!vis[stack[top]]){
			root=stack[top];
			scc++;
			vis[stack[top]]=1;
			dfs2(stack[top]);
		}
		memset(vis,0,sizeof(vis));
		vis[root]=1;
		int ans=num[scc];
		//如果是个连通图,则从根结点可以一次遍历完
		dfs2(root);
		for(int i=1;i<=n;i++)
		if(!vis[i]){
			ans=0;
			break;
		}
		printf("%dn",ans);
	}
	return 0;
}

//tarjan算法求强连通分量,然后求出出度为0的强连通分量的点的个数 
#include
#include
#include
using namespace std;
const int maxn=10000+10,maxm=50000+10;
int head[maxn];
struct node{
	int to,next;
}edge[maxm];
int n,m;
int num[maxn],scc;
//num为强连通中点的个数,sc为强连通分量的个数
int dfn[maxn],low[maxn],index;
int stack[maxn],top;
bool is[maxn];//判断是否在栈中 
bool out[maxn];//记录出度 
int belong[maxn];//记录点在哪个强连通分量中 
void tarjan(int u){
	int v;
	dfn[u]=low[u]=++index;
	stack[top++]=u;
	is[u]=true;
	for(int i=head[u];i!=-1;i=edge[i].next){
		v=edge[i].to;
		if(!dfn[v]){
			tarjan(v);
			if(low[u]>low[v]) low[u]=low[v];
		}
		else if(is[v]&&low[u]>dfn[v])
		low[u]=dfn[v];
	}
	if(dfn[u]==low[u]){
		scc++;
		do{
			v=stack[--top];
			belong[v]=scc;
			num[scc]++;
			is[v]=false;
		}while(u!=v);
	}
}
int main(){
	int u,v;
	while(~scanf("%d%d",&n,&m)){
		//init
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(num,0,sizeof(num));
		//memset(belong,0,sizeof(belong));
		scc=index=top=0;
		memset(head,-1,sizeof(head));
		for(int i=0;i1) ans=0;
		printf("%dn",ans);
	}
	return 0;
}

还有个Garbow算法也是求强连通分量的

未经允许不得转载!POJ2186 Popular Cows 【强连通分量】+【Kosaraju】+【Tarjan】

update

纸上得来终觉浅, 绝知此事须躬行。