判断一个图中任意两个点是否双向,就是判断一个图是不是强连通图,每一个点的Low值都是一样的,换言之low数组值都想等
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int > P; //vector<pair<int,int> > ::iterator iter; // //map<ll,int >mp; //map<ll,int >::iterator p; // typedef struct Node { int form; int to; int nex; int sign; }; Node edge[100000 + 10]; int dfn[10000 + 5],low[10000 + 5],head[10000 + 5],Stack[10000 + 5]; bool vis[10000 + 5]; int tot; int scc_num; int stack_num; int vis_time; void clear() { memset(dfn,-1,sizeof(dfn)); memset(head,-1,sizeof(head)); memset(vis,false,sizeof(vis)); memset(low,0,sizeof(low)); memset(Stack,0,sizeof(Stack)); tot = 0; scc_num = 0; stack_num = 0; vis_time = 0; } void addedge(int u,int v) { edge[tot].form = u; edge[tot].to = v; edge[tot].nex = head[u]; head[u] = tot++; } void tarjan(int v) { dfn[v] = low[v] = ++vis_time; vis[v] = true; Stack[stack_num++] = v; for(int i=head[v];i!=-1;i=edge[i].nex) { int u = edge[i].to; if(dfn[u] == -1) { tarjan(u); low[v] = min(low[u],low[v]); } else if(vis[u]) low[v] = min(low[v],dfn[u]); } int tmp; if(low[v] == dfn[v]) { scc_num++; do { tmp = Stack[--stack_num]; vis[tmp] = false; }while(tmp != v); } } void cal(int n) { for(int i=1;i<=n;i++) if(dfn[i] == -1) tarjan(i); } int main() { int n,m; while(scanf("%d %d",&n,&m), n + m) { clear(); while(m--) { int a,b; scanf("%d %d",&a,&b); addedge(a,b); } cal(n); if(scc_num == 1) puts("Yes"); else puts("No"); } return EXIT_SUCCESS; }