高清做视频在线观看网站,黄骅港鑫海化工招聘,酒水招商网站大全,珠海网站建设网题目描述 在古老的魔兽传说中#xff0c;有两个军团#xff0c;一个叫天灾#xff0c;一个叫近卫。在他们所在的地域#xff0c;有n个隘口#xff0c;编号为1..n#xff0c;某些隘口之间是有通道连接的。其中近卫军团在1号隘口#xff0c;天灾军团在n号隘口。某一天有两个军团一个叫天灾一个叫近卫。在他们所在的地域有n个隘口编号为1..n某些隘口之间是有通道连接的。其中近卫军团在1号隘口天灾军团在n号隘口。某一天天灾军团的领袖巫妖王决定派兵攻打近卫军团天灾军团的部队如此庞大甚至可以填江过河。但是巫妖王不想付出不必要的代价他想知道在不修建任何通道的前提下部队是否可以通过隘口及其相关通道到达近卫军团展开攻击。由于n的值比较大n1000于是巫妖王找到了擅长编程的你 _请你帮他解决这个问题否则就把你吃掉变成他的魔法。为了拯救自己赶紧想办法吧。 输入 输入包含多组每组格式如下。 第一行包含两个整数n,m分别代表n个隘口这些隘口之间有m个通道。 下面m行每行包含两个整数ab表示从a出发有一条通道到达b隘口注意通道是单向的。 输出 如果天灾军团可以不修建任何通道就到达1号隘口那么输出YES否则输出NO。 示例输入 2 1
1 2
2 1
2 1 示例输出 NO
YES提示 #include stdio.h #include stdlib.h #includequeue using namespace std; typedef struct arcnode { int adj; } arcnode, adjmatrix[1000][1000]; typedef struct { adjmatrix a; int vn; int an; } MG; int k;//初始点 int i, j; int create(MG g, int n, int m)//生成邻接矩阵 { int v1, v2; g.vn n; g.an m; for(i1; ig.vn; i) for(j1; jg.vn; j) g.a[i][j].adj 0; for(i1; ig.an; i) { scanf(%d %d, v1, v2); g.a[v1][v2].adj 1; } return 1; } int v[1000];//标记数组 int bfs(MG g)//广度优先遍历 { queueintq;//放在里面 否则超时 for(i0; ig.vn; i)//初始化 v[i] 0; v[g.vn] 1;//从尾结点遍历 q.push(g.vn); while(!q.empty()) { i q.front(); q.pop(); if(i 1)//到顶点1说明天灾军团能到达1号隘口 return 1; for(j1; jg.vn; j) { if(g.a[i][j].adj 1 !v[j]) { v[j] 1; q.push(j); } } } return 0; } int main() { MG g; int n, m; while(~scanf(%d %d, n, m))//主函数里输入 否则超时 { create(g, n, m); bfs(g); if(!bfs(g)) printf(NO\n); else printf(YES\n); } return 0; }
