POJ2762 单向连通图(缩点+拓扑排序

Going from u to v or from v to u?

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 19552		Accepted: 5262

Description

In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

Input

The first line contains a single integer T, the number of test cases. And followed T cases.

The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.

Output

The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.

Sample Input

Sample Output

Yes

Source

POJ Monthly--2006.02.26,zgl & twb

题意: 给你一个有向图,如果对于图中的任意一对点u和v都有一条从u到v的路或从v到u的路,那么就输出’Yes’,否则输出’No’.

分析:

首先求出该图的所有强连通分量，把所有分量缩点，构成一个新的DAG图。现在的问题变成了：该DAG图是否对于任意两点都存在一条路。

多画几个图可以知道该DAG图只能是一条链的时候才行(自己画图验证一下)，用拓扑排序验证(队列中始终只有一个元素)。

代码：

  1 #include"bits/stdc++.h"
  2 
  3 #define db double
  4 #define ll long long
  5 #define vl vector<ll>
  6 #define ci(x) scanf("%d",&x)
  7 #define cd(x) scanf("%lf",&x)
  8 #define cl(x) scanf("%lld",&x)
  9 #define pi(x) printf("%d
",x)
 10 #define pd(x) printf("%f
",x)
 11 #define pl(x) printf("%lld
",x)
 12 #define rep(i, a, n) for (int i=a;i<n;i++)
 13 #define per(i, a, n) for (int i=n-1;i>=a;i--)
 14 #define fi first
 15 #define se second
 16 using namespace std;
 17 typedef pair<int, int> pii;
 18 const int N = 6e3 + 5;
 19 const int mod = 1e9 + 7;
 20 const int MOD = 998244353;
 21 const db PI = acos(-1.0);
 22 const db eps = 1e-10;
 23 const int inf = 0x3f3f3f3f;
 24 const ll INF = 0x3fffffffffffffff;
 25 int in[N];
 26 int out[N];
 27 int head[N],h[N];
 28 int low[N],dfn[N];
 29 int ins[N],beg[N];
 30 int cnt,id,num,cntt;
 31 int n, m, t;
 32 queue<int> q;
 33 stack<int> s;
 34 struct P {
 35     int to, nxt;
 36 } e[2 * N], g[2 * N];
 37 
 38 void add(int u, int v) {//原图
 39     e[cnt].to = v;
 40     e[cnt].nxt = head[u];
 41     head[u] = cnt++;
 42 }
 43 void ADD(int u, int v) {//缩点图
 44     g[cntt].to = v;
 45     g[cntt].nxt = h[u];
 46     h[u] = cntt++;
 47 }
 48 void tarjan(int u)
 49 {
 50     low[u]=dfn[u]=++id;
 51     ins[u]=1;
 52     s.push(u);
 53     for(int i=head[u];~i;i=e[i].nxt){
 54         int v=e[i].to;
 55         if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
 56         else if(ins[v]) low[u]=min(low[u],dfn[v]);
 57     }
 58     if(low[u]==dfn[u]){
 59         int v;
 60         do{
 61             v=s.top();s.pop();
 62             beg[v]=num;
 63             ins[v]=0;
 64         }while(u!=v);
 65         num++;
 66     }
 67 }
 68 bool work()
 69 {
 70     while(!q.empty()) q.pop();
 71     for(int i=0;i<num;i++){
 72         if(!in[i]) q.push(i);
 73 //        if(in[i]>1||out[i]>1) return 0;//链上点出度入度都不大于1
 74     }
 75     int ans=0;
 76     while(!q.empty()){
 77         if(q.size()>1) return 0;
 78         int u=q.front();q.pop();
 79         ans++;
 80         for(int i=h[u];~i;i=g[i].nxt){
 81             int v=g[i].to;
 82             in[v]--;
 83             if(!in[v]) q.push(v);
 84         }
 85     }
 86     return ans==num;//成链
 87 }
 88 void init()
 89 {
 90     cnt = num = id = cntt= 0;
 91     memset(in, 0, sizeof(in));
 92     memset(out, 0, sizeof(out));
 93     memset(head, -1, sizeof(head));
 94     memset(h, -1, sizeof(h));
 95     memset(low,0, sizeof(low));
 96     memset(dfn,0, sizeof(dfn));
 97     memset(ins,0, sizeof(ins));
 98     memset(beg,0, sizeof(beg));
 99 }
100 int main() {
101     ci(t);
102     while(t--)
103     {
104         ci(n),ci(m);
105         init();
106         for (int i = 0; i < m; i++) {
107             int x, y;
108             ci(x), ci(y);
109             add(x, y);
110         }
111         for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
112         for(int i=1;i<=n;i++){
113             for(int j=head[i];~j;j=e[j].nxt){
114                 int v=e[j].to;
115                 if(beg[i]!=beg[v]) out[beg[i]]++,in[beg[v]]++,ADD(beg[i],beg[v]);//缩点后的图
116             }
117         }
118         puts(work()?"Yes":"No");
119     }
120 }