POJ 2762 Going from u to v or from v to u?- Tarjan

Description

判断一个有向图是否对于任意两点 $x$, $y$ 都有一条路径使$x - >y$或 $y - >x$

Solution

对于一个强联通分量内的点都是可以互相到达的。

接下来我们考虑缩点后的DAG是否任意两点都有路径能使一点到达另一点。

然后我就不会了~~

我们进行一遍拓扑排序，如果过程中有超过一个点的入度为 $0$ ，那么就不符合条件（仔细想想好像还是对的

Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<queue>
  5 #define rd read()
  6 #define R register
  7 using namespace std;
  8 
  9 const int N = 1e5;
 10 
 11 int head[N], tot;
 12 int Head[N], Tot;
 13 int dfn[N], low[N], st[N] ,tp, vis[N], cnt;
 14 int col_num, col[N], ru[N];
 15 int n, m, T;
 16 
 17 queue<int> q;
 18 
 19 struct edge {
 20     int nxt, to, fr;
 21 }e[N << 2], E[N << 2];
 22 
 23 int read() {
 24     int X = 0, p = 1; char c = getchar();
 25     for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1;
 26     for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0';
 27     return X * p;
 28 }
 29 
 30 void add(int u, int v) {
 31     e[++tot].to = v;
 32     e[tot].nxt = head[u];
 33     e[tot].fr = u;
 34     head[u] = tot;
 35 }
 36 
 37 void Add(int u, int v) {
 38     E[++Tot].to = v;
 39     E[Tot].nxt = Head[u];
 40     E[Tot].fr = u;
 41     Head[u] = Tot;
 42 }
 43 
 44 bool topsort() {
 45     int num = 0;
 46     for(int i = 1; i <= tot; ++i) {
 47         int u = col[e[i].fr], v = col[e[i].to];
 48         if(u == v) continue;
 49         ru[v]++;
 50         Add(u, v);
 51     }
 52     for(int i = 1; i <= col_num; ++i) 
 53         if(ru[i] == 0) num++, q.push(i);
 54     if(num > 1) 
 55         return 0;
 56     for(int u; !q.empty();) {
 57         if(num > 1) return 0;
 58         u = q.front(); q.pop();
 59         num--;
 60         for(int i = Head[u]; i; i = E[i].nxt) {
 61             int nt = E[i].to;
 62             ru[nt]--;
 63             if(!ru[nt])
 64                 num++, q.push(nt);
 65         }
 66     }
 67     return 1;
 68 }
 69 
 70 void tarjan(int u) {
 71     dfn[u] = low[u] = ++cnt;
 72     st[++tp] = u;
 73     vis[u] = 1;
 74     for(R int i = head[u]; i; i = e[i].nxt) {
 75         int nt = e[i].to;
 76         if(!dfn[nt]) {
 77             tarjan(nt);
 78             low[u] = min(low[u], low[nt]);
 79         }
 80         else if(vis[nt]) low[u] = min(low[u], dfn[nt]);
 81     }
 82     if(low[u] == dfn[u]) {
 83         ++col_num;
 84         for(; tp; ) {
 85             int z = st[tp--];
 86             vis[z] = 0;
 87             col[z] = col_num;
 88             if(z == u) break;
 89         }
 90     }
 91 }
 92 
 93 void init() {
 94     Tot = tp = tot = cnt = col_num = 0;
 95     memset(vis, 0 ,sizeof(vis));
 96     memset(dfn, 0, sizeof(dfn));
 97     memset(col, 0, sizeof(col));
 98     memset(head, 0, sizeof(head));
 99     memset(low, 0, sizeof(low));
100     memset(st, 0, sizeof(tp));
101     memset(Head, 0, sizeof(Head));
102     memset(ru, 0, sizeof(ru));
103     while(!q.empty()) q.pop();
104 }
105 
106 int main()
107 {
108     T = rd;
109     for(; T; T--) {
110         init();
111         n = rd; m = rd;
112         for(int i = 1;  i <= m; ++i) {
113             int u = rd, v = rd;
114             add(u, v);
115         }
116         for(int i = 1; i <= n; ++i) 
117             if(!dfn[i]) tarjan(i);
118         if(topsort()) puts("Yes");
119         else puts("No");
120     }
121 }

View Code