本题题意为:给你n个点m条单向边。
询问这个图是否是符合这个条件的:任意选两个点 u v 、 u可以到达v或者v可以到达u。
如果是的话就输出Yes,否则输出No
传说中的弱连通。
我的做法:
先 强连通缩点 再选一个入度为0的点开始跑一条边的bfs。最后如果所有的点都被标记过那么就是 否则就不是
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <vector> #include <map> #include <queue> #include <set> #include <algorithm> using namespace std; #define MAXN 1010 vector <int> e1[MAXN]; vector <int> e[MAXN]; int dfn[MAXN],low[MAXN],stack[MAXN],bleg[MAXN]; int top,times,n,m; void tarjan_x(int u){ dfn[u]=low[u]=++times; stack[++top]=u; for(int i=0;i<(int)e[u].size();i++){ int v=e[u][i]; if(!dfn[v]){ tarjan_x(v); low[u]=min(low[u],low[v]); } else if(!bleg[v]) low[u]=min(low[u],low[v]); } if(dfn[u]==low[u]){ bleg[0]++; do{ bleg[stack[top]]=bleg[0]; }while(stack[top--]!=u); } } void init(){ memset(dfn,0,sizeof(dfn)); memset(bleg,0,sizeof(bleg)); top=times=0; } void tarjan(int n){ init(); for(int i=1;i<=n;i++) if(!dfn[i])tarjan_x(i); } int ha[MAXN]; void bfs(int u){ queue <int> q; q.push(u); memset(ha,0,sizeof(ha)); ha[u]=1; while(!q.empty()){ int now=q.front(); q.pop(); if(e1[now].empty())continue; int next=e1[now][0]; if(ha[next])continue; ha[next]=1; q.push(next); } } int ru[MAXN]; int main() { int t,cas=0; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<MAXN;i++)e[i].clear(); for(int i=0;i<MAXN;i++)e1[i].clear(); for(int i=0,x,y;i<m;i++){ scanf("%d%d",&x,&y); e[x].push_back(y); } tarjan(n); if(bleg[0]==1){ puts("Yes"); continue; } memset(ru,0,sizeof(ru)); for(int i=1;i<=n;i++){ for(int j=0;j<(int)e[i].size();j++){ int v=e[i][j]; if(bleg[i]!=bleg[v]){ e1[bleg[i]].push_back(bleg[v]); ++ru[bleg[v]]; } } } int flag=0; for(int i=1;i<=bleg[0]&&!flag;i++){ if(!ru[i])flag=i; } bfs(flag); for(int i=1;i<=bleg[0]&&flag;i++){ if(!ha[i])flag=0; } if(flag)puts("Yes"); else puts("No"); } return 0; }
|