T24412 Cup#182-3 洞穴之旅

弱連通模板題，不過還是不會。。。

---

這道題在POJ2762有，這個出題人直接翻譯弄過來了。。。

弱連通的定義是：從u能到達v或從v能到達u，則u和v這兩個點弱連通。

顯然如果是強連通分量就一定是弱連通分量啦，所以可以直接縮點弄掉。

縮點后的DAG中，可能會不符合條件的不可能被我們縮掉。

那么對于這個DAG，發現只有兩個或多個邊連入某個點的話，就不符合這個條件。

所以對一個新圖弄一個toposort，一旦通過同一個點刪邊的過程添加了兩個以上的點的話，就絕對不符合條件。

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
const int maxn = 10005, maxm = 100005;
struct Edges
{int next, from, to;
} e[maxm], e2[maxm];
int head[maxn], tot;
int head2[maxn], tot2;
int n, m;
int dfn[maxn], low[maxn], dtot;
bool vis[maxn];
int color[maxn], ctot;
int indegree[maxn];
std::stack<int> s;
int read()
{int ans = 0, s = 1;char ch = getchar();while(ch > '9' || ch < '0'){if(ch == '-') s = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ans = ans * 10 + ch - '0';ch = getchar();}return s * ans;
}
void init()
{memset(head, 0, sizeof(head));memset(head2, 0, sizeof(head2));memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(color, 0, sizeof(color));memset(indegree, 0, sizeof(indegree));tot = tot2 = dtot = ctot = 0;while(!s.empty()) s.pop();
}
void link(int u, int v)
{e[++tot] = (Edges){head[u], u, v};head[u] = tot;
}
void link2(int u, int v)
{e2[++tot2] = (Edges){head2[u], u, v};head2[u] = tot2;
}
void tarjan(int u)
{dfn[u] = low[u] = ++dtot;s.push(u); vis[u] = true;for(int i = head[u]; i; i = e[i].next){int v = e[i].to;if(!dfn[v]){tarjan(v);low[u] = std::min(low[u], low[v]);}else if(vis[v]) low[u] = std::min(low[u], dfn[v]);}if(low[u] == dfn[u]){ctot++;while(s.top() != u){int x = s.top(); s.pop();vis[x] = false; color[x] = ctot;}int x = s.top(); s.pop();vis[x] = false; color[x] = ctot;}
}
bool toposort()
{std::queue<int> q;int cnt = 0, count = 0;for(int i = 1; i <= ctot; i++){if(indegree[i] == 0){q.push(i);cnt++;}}if(cnt > 1) return false;while(!q.empty()){count++;cnt = 0;int u = q.front(); q.pop();for(int i = head2[u]; i; i = e2[i].next){int v = e2[i].to;indegree[v]--;if(indegree[v] == 0){q.push(v); cnt++;}}if(cnt > 1) return false;}if(count == ctot) return true;
}
int main()
{//freopen("in.txt", "r", stdin);int T = read();while(T--){init();n = read(), m = read();while(m--){int u = read(), v = read();link(u, v);}for(int i = 1; i <= n; i++){if(!dfn[i]) tarjan(i);}//for(int i = 1; i <= n; i++) printf("%d\n", color[i]);for(int i = 1; i <= tot; i++){int u = e[i].from, v = e[i].to;if(color[u] != color[v]){link2(color[u], color[v]);indegree[color[v]]++;}}if(toposort()) printf("Yes\n");else printf("No\n");}return 0;
}