百度城市服务小程序_开源建站系统cms_江阴企业网站制作_我要安装百度

105. 有向图的完全可达性

这道题属于简单搜索题，采用bfs即可，也可用dfs但注意要回溯

1、条件准备

graph数组存图，visit数组判断结点是否走过。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
#define endl '\n'bool graph[105][105];
bool visit[105];int n,k;

2、主函数

先存图，建边。然后bfs

再遍历一下结点是否都走过，有没走过输出-1，否则输出1

int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>k;rep(i,1,k){int a,b;cin>>a>>b;graph[a][b]=1;}bfs(); rep(i,1,n){if(!visit[i]){cout<<"-1";return 0;}}cout<<"1";return 0;
}

3、bfs函数

还是用数组模拟队列，把1放进去。

取队头，遍历该点有无边，并且还没走过，有就加入队列。

void bfs()
{int q[105];int tt=-1,hh=0;q[++tt]=1;visit[1]=1;while(hh<=tt){int cur=q[hh++];rep(i,1,n){if(graph[cur][i]&&!visit[i]){q[++tt]=i;visit[i]=1;}}}
}

4、总结

简单搜索题

完整代码如下：

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
#define endl '\n'bool graph[105][105];
bool visit[105];int n,k;void bfs()
{int q[105];int tt=-1,hh=0;q[++tt]=1;visit[1]=1;while(hh<=tt){int cur=q[hh++];rep(i,1,n){if(graph[cur][i]&&!visit[i]){q[++tt]=i;visit[i]=1;}}}
}
int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>k;rep(i,1,k){int a,b;cin>>a>>b;graph[a][b]=1;}bfs(); rep(i,1,n){if(!visit[i]){cout<<"-1";return 0;}}cout<<"1";return 0;
}