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

---

這道題在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; }

轉載于:https://www.cnblogs.com/Garen-Wang/p/9461792.html

總結

以上是生活随笔為你收集整理的T24412 Cup#182-3 洞穴之旅的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。