POJ 2762 Going from u to v or from v to u?
题意:给定一些有向图,要判断该图是否满足任意两点,要么u能到v,要么v能到u
思路:先缩点,然后拓扑排序,排序过程中如果队列中有任意时刻点大于2个,就代表出现分支了,肯定就不行了
代码:
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <stack> #include <queue> using namespace std; const int N = 1005; int t, n, m, vis[N][N]; vector<int> g[N], scc[N]; stack<int> S; int pre[N], dfn[N], dfs_clock, sccn, sccno[N]; void dfs_scc(int u) { pre[u] = dfn[u] = ++dfs_clock; S.push(u); for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!pre[v]) { dfs_scc(v); dfn[u] = min(dfn[u], dfn[v]); } else if (!sccno[v]) dfn[u] = min(dfn[u], pre[v]); } if (dfn[u] == pre[u]) { sccn++; while (1) { int x = S.top(); S.pop(); sccno[x] = sccn; if (x == u) break; } } } void find_scc() { sccn = dfs_clock = 0; memset(pre, 0, sizeof(pre)); memset(sccno, 0, sizeof(sccno)); for (int i = 1; i <= n; i++) if (!pre[i]) dfs_scc(i); } int in[N]; int main() { scanf("%d", &t); while (t) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) g[i].clear(); int u, v; while (m--) { scanf("%d%d", &u, &v); g[u].push_back(v); } find_scc(); memset(in, 0, sizeof(in)); for (int i = 1; i <= sccn; i++) scc[i].clear(); for (int u = 1; u <= n; u++) { for (int j = 0; j < g[u].size(); j++) { int v = g[u][j]; int su = sccno[u], sv = sccno[v]; if (su == sv || vis[su][sv] == t) continue; vis[su][sv] = t; in[sv]++; scc[su].push_back(sv); } } queue<int> Q; for (int i = 1; i <= sccn; i++) if (!in[i]) Q.push(i); while (Q.size() == 1) { int u = Q.front(); Q.pop(); for (int i = 0; i < scc[u].size(); i++) { int v = scc[u][i]; in[v]--; if (in[v] == 0) Q.push(v); } } printf("%s\n", Q.empty() ? "Yes" : "No"); t--; } return 0; }