题意找 一个图是否 任意两点都可以从 u 到v 或者 从v到u 注意是或者 所以不是一个简单的强连通图
思路 ： 先找出这个图的 强连通分量 在强连通分量里任意两点都是可以互相到达的 再看 缩点后 在拓扑排序时是否入度为0 的点一直会《=1 若中间有一步 发现入度为0 的点>=2 就直接可以判断这两个点 热河一个点都到达不了对方 应该输出 no
代码有点长 再次提醒自己 细心！
#include<iostream> #include<vector> #include<string.h> #include<stack> using namespace std; int pre[1002],low[1002],c,sccnum[1002],degree[1002],scc,n; vector <int > g[1002],gg[1002]; stack <int > s; int min(int a,int b) { return a<b?a:b; } int dfs(int u) { s.push (u); low[u]=pre[u]=c++; for(int i=0;i<g[u].size ();i++) { int v=g[u][i]; if(!pre[v]) { int lowv=dfs(v); low[u]=min(low[u],lowv); } else if(sccnum[v]==0) low[u]=min(low[u],pre[v]); } if(pre[u]==low[u]) { scc++; while(1) { int t=s.top (); s.pop(); sccnum[t]=scc; if(u==t) break; } } return low[u]; } int solve() { int i,j,cur; for(i=1;i<=scc;i++) gg[i].clear (); //注意这里 两个容器不要搞混了。。 memset(degree,0,sizeof(degree)); for(i=1;i<=n;i++) for(j=0;j<g[i].size ();j++) { int v=g[i][j]; if(sccnum[i]!=sccnum[v]) { degree[sccnum[v]]++; //入度 gg[sccnum[i]].push_back (sccnum[v]); } //记录每个缩点的 入度 } int cnt=0; for(i=1;i<=scc;i++) if(degree[i]==0) { cnt++; cur=i; if(cnt>1) //一旦在某一步发现 入度为0 的 点超过了1 就直接跳出 return 0; } int num=scc,temp=-1; while(num--) // { cnt=0; for(i=0;i<gg[cur].size ();i++) { int v=gg[cur][i]; degree[v]--; if(degree[v]==0) { cnt++; if(cnt>1) return 0; temp=v; } } cur=temp; } return 1; } int main() { int t,m,a,b,i,p=1; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) g[i].clear(); while(m--) { scanf("%d%d",&a,&b); g[a].push_back (b); } memset(pre,0,sizeof(pre)); memset(sccnum,0,sizeof(sccnum)); int cnt=0; c=1; scc=0; for(i=1;i<=n;i++) if(!pre[i]) dfs(i);//printf("ok "); int ww=solve(); if(ww==0) printf("No "); else printf("Yes "); } return 0; }