迷宫城堡(HDU 1269)---求强连通分量模板题

题目链接

题目描述

为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。

输入格式

输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。

输出格式

对于输入的每组数据，如果任意两个房间都是相互连接的，输出"Yes"，否则输出"No"。

输入样例

3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0

输出样例

Yes
No

分析

题目大意是求强连通分量，判断是不是强连通分量个数是不是为1？
直接套用tarjan算法或者Korasaju算法模板即可，以下是源码。

源程序

tarjan算法

#include 
#define MAXN 10005
using namespace std;
struct Edge{	//链式前向星 int v,next;Edge(){};Edge(int _v,int _next){v=_v,next=_next;}
}edge[MAXN*10]; 
int EdgeCount,head[MAXN];
int n,m,cnt,color;
int dfn[MAXN],low[MAXN],num[MAXN];
bool vis[MAXN];
stack <int> s;
void addEdge(int u,int v)	//链式前向星建图 
{edge[++EdgeCount]=Edge(v,head[u]);head[u]=EdgeCount;
}
int read()	//快读 
{int sum=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();} return sum;
}
void init()	//初始化 
{memset(head,0,sizeof(head));	memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(num,0,sizeof(num));memset(vis,false,sizeof(vis));EdgeCount=cnt=color=0;
}
void tarjan(int u)
{dfn[u]=low[u]=++cnt;	//打上时间戳 vis[u]=true;	//标记入栈 s.push(u);	//入栈for(int i=head[u];i;i=edge[i].next){	//遍历相邻节点 int v=edge[i].v;if(!vis[v]){	//未被访问过tarjan(v);low[u]=min(low[u],low[v]); }else if(vis[u])					//已经访问过但在栈中 low[u]=min(low[u],dfn[v]);	//在判断强连通分量是用dfn还是low其实没影响}									//但在求割点时，用low[v]比较会漏掉割点	if(dfn[u]==low[u]){	 //满足强连通分量要求color++;	//记录强连通分量个数while(1){int tmp=s.top();s.pop();num[tmp]=color;		//标记所属强连通分量 if(tmp==u)break;} } 
}
int main()
{while(1){init(); n=read(),m=read();if(!n&&!m)break;for(int i=1;i<=m;i++){int u=read(),v=read();addEdge(u,v);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);	if(color==1)printf("Yes\n");else printf("No\n");}
}

Kosaraju算法

#include 
#define MAXN 10005
using namespace std;
struct Edge{	//链式前向星 int v,next;Edge(){};Edge(int _v,int _next){v=_v,next=_next;}
}; 
struct GNode{int EdgeCount,head[MAXN];Edge edge[MAXN*10];void clear(){memset(head,0,sizeof(head));EdgeCount=0;}void addEdge(int u,int v){	//链式前向星建图 edge[++EdgeCount]=Edge(v,head[u]);head[u]=EdgeCount;}
}; 
GNode G,GT;
bool vis[MAXN];
int n,m,cnt,color,dfn[MAXN],num[MAXN];
stack <int> s;
int read()	//快读 
{int sum=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();} return sum;
}
void init()	//初始化 
{memset(dfn,0,sizeof(dfn));memset(num,0,sizeof(num));G.clear();GT.clear();
}
void dfs1(int u)	//第一次深搜记录搜索完成时间 
{vis[u]=true;for(int i=G.head[u];i;i=G.edge[i].next){int v=G.edge[i].v;if(!vis[v])	//没有访问过 dfs1(v);}dfn[++cnt]=u;	//记录完成时间 
}
void dfs2(int u)	//第二次深搜记录强连通分量 
{vis[u]=true;num[u]=color;for(int i=GT.head[u];i;i=GT.edge[i].next){int v=GT.edge[i].v;if(!vis[v])dfs2(v);}
} 
void Kosaraju()
{/*第一次深搜*/ cnt=0;	//时间戳 memset(vis,false,sizeof(vis));for(int i=1;i<=n;i++)if(!vis[i])dfs1(i);/*第二次深搜*/color=0;	//记录强连通分量个数memset(vis,false,sizeof(vis));for(int i=n;i>=1;i--){if(!vis[dfn[i]]){color++;dfs2(dfn[i]);}} 
}
int main()
{while(1){init(); n=read(),m=read();if(!n&&!m)break;for(int i=1;i<=m;i++){int u=read(),v=read();G.addEdge(u,v);GT.addEdge(v,u);}Kosaraju();if(color==1)printf("Yes\n");else printf("No\n");}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！