首页 > 代码库 > UVALive4287-- Proving Equivalences(SCC+Tarjan)
UVALive4287-- Proving Equivalences(SCC+Tarjan)
题目链接
题意:证明n个命题全部等价,已经给出m此推导,求至少还要几次推导才能完成整个证明。
思路:可以将命题看作结点,推导看作有向边,则本题就能转化为n个结点m条边的有向图。利用tarjan算法得到所有强连通分量,将这些强连通分量当作一个点,得到一个DAG。之后就可以求次数了。注意当强连通数量为1时,就代表着证明已经完成了。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <stack> #include <algorithm> using namespace std; const int MAXN = 20005; vector<int> g[MAXN]; stack<int> s; int pre[MAXN], lowlink[MAXN], sccno[MAXN], dfs_clock, scc_cnt; int in[MAXN], out[MAXN]; int n, m; int Tarjan(int u) { pre[u] = lowlink[u] = ++dfs_clock; s.push(u); for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!pre[v]) { Tarjan(v); lowlink[u] = min(lowlink[u], lowlink[v]); } else if (!sccno[v]) { lowlink[u] = min(lowlink[u], pre[v]); } } if (lowlink[u] == pre[u]) { scc_cnt++; for (;;) { int x = s.top(); s.pop(); sccno[x] = scc_cnt; if (x == u) break; } } } void find_scc() { memset(pre, 0, sizeof(pre)); memset(sccno, 0, sizeof(sccno)); memset(lowlink, 0, sizeof(lowlink)); dfs_clock = scc_cnt = 0; for (int i = 0; i < n; i++) if (!pre[i]) Tarjan(i); } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) g[i].clear(); int u, v; for (int i = 0; i < m; i++) { scanf("%d%d", &u, &v); u--; v--; g[u].push_back(v); } find_scc(); memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); for (int i = 1; i <= scc_cnt; i++) in[i] = out[i] = 1; for (int u = 0; u < n; u++) for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (sccno[u] != sccno[v]) in[sccno[v]] = out[sccno[u]] = 0; } int a = 0, b = 0; for (int i = 1; i <= scc_cnt; i++) { if (in[i]) a++; if (out[i]) b++; } int ans = max(a, b); if (scc_cnt == 1) ans = 0; printf("%d\n", ans); } return 0; }
UVALive4287-- Proving Equivalences(SCC+Tarjan)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。