3 solutions
-
3
#include <iostream> #include <vector> #include <stack> using namespace std; const int N = 2e4 + 5; int dfn[N], low[N]; // 时间戳,追溯值 vector<int> g[N]; // 存图 vector<int> vbcc[N]; // 点双连通分量 int belong[N]; // 记录某点属于哪个SCC stack<int> stk; // Tarjan用到的临时栈 int n, m, t, numVbcc; bool ap[N]; // 割点标记数组 int apcnt; int root; // 特殊处理根节点是割点的情况 void tarjan(int x) { dfn[x] = low[x] = ++t; stk.push(x); // 根据定义,孤立点也是一个点双,但一定不是割点!!! if (x == root && g[x].size() == 0) { vbcc[++numVbcc].push_back(x); return; } // 记录搜索树内满足割点判定条件的子节点的数量 int son = 0; for (auto y : g[x]) { // 非树边都可以用。重边和父节点都不用处理 if (dfn[y]) { low[x] = min(low[x], dfn[y]); continue; } // if (!dfn[y]) // (x,y)是树边 son++; tarjan(y); low[x] = min(low[x], low[y]); // 满足点双判定法则 if (low[y] >= dfn[x]) { // 只有非根 || 是根且子节点个数>=2才是割点 if (x != root || son >= 2) { // 计算割点时一定要注意!!!可能会重复计算割点!!! // 如果用标记数组,那么就要这样统计个数。 // 如果用vector,那么一定要记得排序去重!!! apcnt += !ap[x]; ap[x] = 1; } // 点双处理,别忘了x本身,它可能属于多个点双 vbcc[++numVbcc].push_back(x); int z; do { // 不管是不是割点,一定形成了一个包含x的点双 z = stk.top(); stk.pop(); vbcc[numVbcc].push_back(z); } while (y != z); // 要保证x不被弹出(允许x属于多个点双) } } } int main() { cin >> n >> m; int u, v; for (int i = 1; i <= m; i++) { cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } // 大部分用Tarjan算法的题都要这样写!一定要注意!!! for (int i = 1; i <= n; i++) if (!dfn[i]) root = i, tarjan(i); cout << apcnt << '\n'; for (int i = 1; i <= n; i++) if (ap[i]) cout << i << ' '; return 0; }
-
2
我发个只求割点的
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e4 + 5,M = 1e5 + 5; int n,m,dfn[N],low[N],tot,sum; vector<int> g[N]; bool ans[N]; void tarjan(int u,int fa){ dfn[u] = ++tot;low[u] = tot; bool flag = 0; int cnt = 0; for (int v : g[u]){ if (!dfn[v]){ tarjan(v,u),low[u] = min(low[u],low[v]); if (low[v] >= dfn[u]) cnt++; // 防重复算 } else if (v != fa || flag) low[u] = min(low[u],dfn[v]); else flag = 1; } if (cnt && fa || cnt > 1 && !fa) ans[u] = 1; } int main(int argc, char **argv){ cin >> n >> m; for (int i = 1;i <= m;i++){ int u,v; cin >> u >> v; if (u == v) continue; g[u].push_back(v); g[v].push_back(u); } for (int i = 1;i <= n;i++){ if (!dfn[i]) tarjan(i,0); } for (int i = 1;i <= n;i++){ if (ans[i]) sum++; } cout << sum << '\n'; for (int i = 1;i <= n;i++){ if (ans[i]) cout << i << ' '; } return 0; }
-
-2
// 别说, 我的马蜂跟 @zengfj 还有几分相似 #include <cstdio> #include <algorithm> #include <vector> #include <stack> #define N 20005 using namespace std; int dfn[N], low[N], n, m, x, y, t = 0, apcnt = 0; // dfn 时间戳 // low 追溯值 // t 时间戳计数 // apcnt 割点个数 vector<int> g[N], aps; // g 存图 // aps 存割点 vector<vector<int> > vbccs; // 点双 bool is_ap[N]; // 是否为割点 stack<int> s; // 栈 // 模板, 自己看 PPT void tarjan(int x, int root) { dfn[x] = low[x] = ++t; s.push(x); // 是根并且没有边 if (x == root && !g[x].size()) { vbccs.push_back(vector<int>(1, x)); return; } int son = 0; for (const auto& y : g[x]) { // 非树边都可以用。重边和父节点都不用处理 if (dfn[y]) { low[x] = min(low[x], dfn[y]); continue; } son++; tarjan(y, root); low[x] = min(low[x], low[y]); if (low[y] >= dfn[x]) { // 非根 or 子节点个数大于 1 if (x != root || son > 1) { // 记得去重, 我直接打标记 apcnt += !is_ap[x]; is_ap[x] = true; } // 记录答案 vbccs.push_back(vector<int>(1, x)); int z; do { z = s.top(); s.pop(); vbccs.back().push_back(z); } while (y != z); // x 不要出栈 } } } int main() { scanf("%d%d", &n, &m); while (m--) { scanf("%d%d", &x, &y); g[x].push_back(y); g[y].push_back(x); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, i); for (int i = 1; i <= n; i++) if (is_ap[i]) aps.push_back(i); sort(aps.begin(), aps.end()); printf("%d\n", (int)aps.size()); for (const auto& i : aps) printf("%d ", i); return 0; }
- 1
Information
- ID
- 416
- Time
- 1000ms
- Memory
- 125MiB
- Difficulty
- 7
- Tags
- # Submissions
- 61
- Accepted
- 14
- Uploaded By