宁德市住房和城乡建设局新网站,国外赚钱平台,网站根目录有哪些,网站添加广告源码题干#xff1a;
为了训练小希的方向感#xff0c;Gardon建立了一座大城堡#xff0c;里面有N个房间(N10000)和M条通道(M100000)#xff0c;每个通道都是单向的#xff0c;就是说若称某通道连通了A房间和B房间#xff0c;只说明可以通过这个通道由A房间到达B房间…题干
为了训练小希的方向感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 0
Sample Output
Yes
No
解题报告 这题做法很多也可以直接暴力跑每个节点是否可以连通其他节点也可以直接跑tarjan算法看是否只有一个强连通分量。 AC代码
#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];
stackint sk;
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;sk.push(x);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;while(1) {int now sk.top();sk.pop();vis[now]0;if(now x) break;}}}
int main()
{int a,b;while(~scanf(%d%d,n,m)) {if(n 0 m 0) break;top tot cnt 0;while(sk.size()) sk.pop();memset(head,-1,sizeof head);memset(vis,0,sizeof vis);for(int i 1; in; i) dfn[i] low[i] 0;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 ;
}
直接暴力AC代码2
//hdu1269(迷宫城堡判断有向图是否联通)
//题目大意已知有n(n10000)个点M(M100000)个道路。每条道路都是单向的。求任意两个点之间是否联通
//解题思路由于点n的范围较大所以用邻接表存储n个点的道路情况。然后依次搜索n各点能否
//到达剩余的n-1个点。如果有一个不满足就退出循环。表示该有向图不是联通图。否则就是。
//这里我用的是dfs搜索看是否某个点能否到达其余的n-1个点。
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int n,m,head[100010],k,flag,vis[10010],cnt,gg;
struct node {int x,y;int next;
} edge[100010];
void init() { //初始化邻接表k0;memset(head,-1,sizeof(head));
}
void input() { //读取数据init();int i,j,x,y;for(i0; im; i) {scanf(%d%d,x,y);edge[k].xx;edge[k].yy;edge[k].nexthead[x]; //建x到y的边。head[x]k;}
}
void dfs(int x) {int v,i;if(cntn-1) {//可以到达其余的n-1个点gg1;return; } for(ihead[x]; i!-1; iedge[i].next) {vedge[i].y;if(!vis[v]) {vis[v]1;cnt; //cnt用来记录从某点出发所能到达的点数dfs(v);if(gg) return;}}
}
int main() {int i,j;while(scanf(%d%d,n,m)(n|m)) {input();flag1;for(i1; in; i) {cnt0;gg0;memset(vis,0,sizeof(vis));vis[i]1; //标记idfs(i); //搜索i所能到达的点的个数。if(cntn-1) {flag0;break; //有一个点到其余各点不是n-1时则该图不联通。} //退出循环}if(flag1) printf(Yes\n);else printf(No\n);}return 0;
}
新的算法kosaraju算法https://blog.csdn.net/qq7366020/article/details/12943345
//Final kosaraju判断有向图是否为强联通图
#include stdio.h
#include string.h
#include stdlib.h
#define MAX 10100
struct snode{int to,next;
}edge1[MAX*30],edge2[MAX*30],edge3[MAX*30];
int visit1[MAX],In[MAX],To[MAX],pre1[MAX],pre2[MAX],Index1,Index2,k,list[MAX];
int father[MAX];
void Add_edge1(int a,int b) //建立正向图
{edge1[Index1].tob,edge1[Index1].nextpre1[a];pre1[a]Index1;
}void Add_edge2(int a,int b) //建立逆向图
{edge2[Index2].tob,edge2[Index2].nextpre2[a];pre2[a]Index2;
}void Kosaraju(int u) //第一次正向图搜索
{int i,v;for(ipre1[u];i!-1;iedge1[i].next){vedge1[i].to;if(visit1[v]0){visit1[v]1;Kosaraju(v);}}list[k]u;
}void DFS(int u,int Father) //第二次逆向图搜索
{int i,v;visit1[u]2;father[u]Father;for(ipre2[u];i!-1;iedge2[i].next){vedge2[i].to;if(visit1[v]1)DFS(v,Father);}
}int main()
{int n,m,i,j,a,b,c,pd;while(scanf(%d%d,n,m)!EOF){if(n0m0)break;Index1Index20;memset(In,0,sizeof(In));memset(pre1,-1,sizeof(pre1));memset(pre2,-1,sizeof(pre2));memset(visit1,0,sizeof(visit1));memset(father,0,sizeof(father));for(i0;im;i){scanf(%d%d,a,b);Add_edge1(a,b);Add_edge2(b,a);}for(i1,k0;in;i){if(!visit1[i]){visit1[i]1;Kosaraju(i);}}for(jk-1,c0;j0;j--) //第二次搜索和第一次搜索顶点的顺序一样{if(visit1[list[j]]1){DFS(list[j],c);}}for(i1,pd0;in;i) //有两个联通块就说明不是联通图if(father[i]!father[i1])pd1;if(pd0)printf(Yes\n);elseprintf(No\n);}return 0;
}其实这题还是可以用并查集做的AC代码https://blog.csdn.net/wyjwyl/article/details/49369085
#includecstdio
#includecstring
#define maxn 1000010
int rec[3][maxn];
int n,m;
void init()
{for(int i1;i2;i){for(int j1;jn;j)rec[i][j]j;}
}
int find(int x,int i)
{return xrec[i][x]?x:rec[i][x]find(rec[i][x],i);
}
void merge(int a,int b)
{if(a!n){int fafind(a,1);int fbfind(b,1);if(fa!fb)rec[1][a]b;//合并到后面的那个元素身上}if(b!n){int fafind(a,2);int fbfind(b,2);if(fa!fb)rec[2][b]a;//合并到前面的那个元素上}
}
int main()
{int a,b;while(scanf(%d%d,n,m)(n||m)){int flag1;init();for(int i1;im;i){scanf(%d%d,a,b);merge(a,b);}for(int i1;in;i){if(find(i,1)!n||find(i,2)!n){flag0;break;}}if(flag)puts(Yes);elseputs(No);}return 0;
}超时代码
#includecstdio
#includealgorithm
#includecstring
#includeiostream
using namespace std;
const int MAXN 10000 5;
const int MAXM 100000 5;
int n,m;
int top,flag;
int head[MAXN];
bool vis[MAXN];
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 dfs(int x,int cnt) {if(x 1 cnt n1) {
// for(int i head[x]; i!-1; ie[i].ne) {
// if(e[i].to 1) {
// flag 1;break;
// }
// }flag1;return ;}for(int i head[x]; i!-1; ie[i].ne) {if(vis[e[i].to] e[i].to ! 1) continue;vis[e[i].to]1;dfs(e[i].to,cnt1);if(flag) return;vis[e[i].to] 0;}
}
int main()
{int a,b;while(~scanf(%d%d,n,m)) {if(n 0 m 0) break;top flag 0;memset(head,-1,sizeof head);memset(vis,0,sizeof vis);for(int i 1; im; i) {scanf(%d%d,a,b);add(a,b);}dfs(1,1);if(flag) puts(Yes);else puts(No);}return 0 ;
}
总结 这件事情告诉我们一个道理。。。。不带回溯的dfs要比带回溯的dfs快的多的多的多因为不带回溯的是一遍on带回溯的是n
