POJ 2553 The Bottom of a Graph(强连通分量)
The of poj Graph 连通 分量
2023-09-14 09:09:00 时间
POJ 2553 The Bottom of a Graph
题意:给定一个有向图,求出度为0的强连通分量
思路:缩点搞就可以
代码:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <stack> using namespace std; const int N = 5005; int n, m; vector<int> g[N], save[N]; stack<int> S; int pre[N], dfn[N], dfs_clock, sccno[N], sccn; 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++; save[sccn].clear(); while (1) { int x = S.top(); S.pop(); save[sccn].push_back(x); sccno[x] = sccn; if (x == u) break; } } } void find_scc() { dfs_clock = sccn = 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 out[N]; int ans[N], an; int main() { while (~scanf("%d", &n) && n) { for (int i = 1; i <= n; i++) g[i].clear(); scanf("%d", &m); int u, v; while (m--) { scanf("%d%d", &u, &v); g[u].push_back(v); } find_scc(); memset(out, 0, sizeof(out)); for (int i = 1; i <= n; i++) { for (int j = 0; j < g[i].size(); j++) { int v = g[i][j]; if (sccno[i] != sccno[v]) { out[sccno[i]]++; } } } an = 0; for (int i = 1; i <= sccn; i++) { if (!out[i]) { for (int j = 0; j < save[i].size(); j++) ans[an++] = save[i][j]; } } sort(ans, ans + an); for (int i = 0; i < an; i++) printf("%d%c", ans[i], i == an - 1 ? '\n' : ' '); } return 0; }
相关文章
- 《The Joy of Javascript》- 2 - Functor/Monad
- 【错误记录】Flutter 编译报错 ( The parameter ‘‘ can‘t have a value of ‘null‘ because of its type, but the im )
- 【Vue-Spring跨域Bug已解决】has been blocked by CORS policy: The value of the······
- ORA-01311: Illegal invocation of the mine_value function ORACLE 报错 故障修复 远程处理
- ORA-22900: the SELECT list item of THE subquery is not a collection type ORACLE 报错 故障修复 远程处理
- ORA-31128: The event handler calls cannot exceed the depth of string ORACLE 报错 故障修复 远程处理
- ORA-46011: The value of the “selectPrivilege” element is too long. ORACLE 报错 故障修复 远程处理
- ORA-46014: The value of the “aclFile” element is too long. ORACLE 报错 故障修复 远程处理
- ORA-53010: The value of the tag is null. ORACLE 报错 故障修复 远程处理
- ORA-02324: more than one column in the SELECT list of THE subquery ORACLE 报错 故障修复 远程处理
- ORA-06809: TLI Driver: could not clear the IPX ethernet SAP at init ORACLE 报错 故障修复 远程处理
- MySQL: A Powerful Database.MySQL: Unlock the Power of Database Technology(mysql1)
- Cacti: Unleashing the Power of Linux(cactilinux)
- Reap the Benefits of Using MySQL WITH Clause(mysqlwith)
- The Power of Linux: Unleashing the Potential of OpenSource Software(linux英文)
- The Benefits of TLS on Linux Systems(linuxtls)
- MySQL 5.7.17:The Latest Upgrade of the Database System(mysql5.7.17)
- nUnlocking the Power of Oracle: Unlocking All Possibilities(oracleu)
- 「Linux 录屏软件下载」功能强大,操作简单!(Note: The translation of the title can be read as Linux Screen Recording Software Download: Powerful Functionality Simple Operation! (linux录屏软件下载)
- The Power of the Hydra Oracle: Unlocking Potential(hydraoracle)
- Leading the Way with Oracle Technology(leadoracle)
- Exploring the Power of Linux with D L: A Comprehensive Guide(linuxdl)
- Exploring the Depths of Linux: The Power of the l Command(linux-l)
- TQ2440 Linux: Unleashing the Power of Embedded Computing(tq2440linux)
- Exploring the Power of Flex on Linux: A Comprehensive Guide(linuxflex)
- Exploring the Power of as86 Linux: The Ultimate Guide for Beginners!(as86linux)
- Exploring the Versatile Capabilities of Linux Qume: A Comprehensive Guide(linuxqume)