德阳如何做百度的网站,十堰做网站公司,网站建设与设计意义,wordpress 又拍云HDU1269 迷宫城堡 文章目录Problem Description题解#xff1a;Problem Description
为了训练小希的方向感#xff0c;Gardon建立了一座大城堡#xff0c;里面有N个房间(N10000)和M条通道(M100000)#xff0c;每个通道都是单向的#xff0c;就是说若称某通道连通…HDU1269 迷宫城堡
文章目录Problem Description题解Problem Description
为了训练小希的方向感Gardon建立了一座大城堡里面有N个房间(N10000)和M条通道(M100000)每个通道都是单向的就是说若称某通道连通了A房间和B房间只说明可以通过这个通道由A房间到达B房间但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的即对于任意的i和j至少存在一条路径可以从房间i到房间j也存在一条路径可以从房间j到房间i。
Input 输入包含多组数据输入的第一行有两个数N和M接下来的M行每行有两个数a和b表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。
Output 对于输入的每组数据如果任意两个房间都是相互连接的输出Yes否则输出No。 Sample Input
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0Sample Output
Yes
No题解
问这个图是不是只有一个强连通图。 tarjan求强连通分量的模板题 建议背诵 tarjan不清楚的可以看我另一个博客详细的讲解 链式前项星版
#includecstdio
#includestack
#includealgorithm
#includecstring
#includeiostream
using namespace std;
const int MAXN 10000 5;
const int MAXM 100000 5;
int n,m;
int top,tot,cnt;
int head[MAXN];
bool vis[MAXN];
int dfn[MAXN],low[MAXN];
void init()
{toptot cnt 0;memset(head,-1,sizeof head);memset(vis,0,sizeof vis);for(int i 1; in; i) dfn[i] low[i] 0;
}
struct Edge {int to,ne;
}e[MAXM];
void add(int u,int v) {e[top].to v;e[top].ne head[u];head[u] top;
}
void tarjan(int x) {low[x] dfn[x] tot;vis[x] 1;for(int i head[x]; i!-1; ie[i].ne) {int v e[i].to;if(dfn[v] 0) {tarjan(v);low[x] min(low[x],low[v]);}else if(vis[v] 1) {low[x] min(low[x],dfn[v]);}}if(low[x] dfn[x]) cnt;}
int main()
{int a,b;while(~scanf(%d%d,n,m)) {if(n 0 m 0) break;for(int i 1; im; i) {scanf(%d%d,a,b);add(a,b);}for(int i 1; in; i) {if(dfn[i] 0) tarjan(i);}if(cnt 1) puts(Yes);else puts(No);}return 0 ;
}二维矩阵版
#includebits/stdc.h
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
int n,m;
const int maxn100004;
int low[maxn],dfn[maxn];
int vis[maxn];
vectorintmp[maxn];
int cnt0;
int sign;
void init()
{mem(low);mem(dfn);mem(vis);mem(mp);cnt0;sign0;}
void Tarjan(int u)
{vis[u]1;low[u]dfn[u]cnt;for(int i0;imp[u].size();i){int vmp[u][i];if(dfn[v]0){Tarjan(v);low[u]min(low[u],low[v]);}else if(vis[v]1)low[u]min(low[u],dfn[v]);}if(dfn[u]low[u])sign;
}
int main()
{while(cinnm){if(n0m0)break;init();for(int i1;im;i){ int x,y;cinxy;mp[x].push_back(y);}for(int i1;in;i){if(dfn[i]0)Tarjan(i);}if(sign!1)coutNoendl;else coutYesendl;}return 0;
}
