1 solutions
-
1
想说一下处理重边的一种方法:给边加编号id,思路就是“不用来时的边更新”。具体操作见代码。
#include <iostream> #include <vector> #include <stack> using namespace std; // (点编号, 父边的编号) using pii = pair<int, int>; const int N = 5e5 + 5; int dfn[N], low[N]; // 时间戳,追溯值 vector<pii> g[N]; // 存图 vector<int> ebcc[N]; // 边双连通分量 //int belong[N]; // 记录某点属于哪个分量 stack<int> stk; // Tarjan用到的临时栈 int n, m, t, numEbcc; void tarjan(int x, int id) { dfn[x] = low[x] = ++t; stk.push(x); for (auto [y, id2] : g[x]) { if (!dfn[y]) { tarjan(y, id2); low[x] = min(low[x], low[y]); } else if (id2 != id) { // 不用来时的边更新 low[x] = min(low[x], dfn[y]); } } if (low[x] == dfn[x]) { numEbcc++; int y; do { y = stk.top(); stk.pop(); ebcc[numEbcc].push_back(y); } while (y != x); } } int main() { cin >> n >> m; int u, v; for (int i = 1; i <= m; i++) { cin >> u >> v; // 给边加上编号 g[u].push_back({v, i}); g[v].push_back({u, i}); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, -1); cout << numEbcc << '\n'; for (int i = 1; i <= numEbcc; i++) { cout << ebcc[i].size() << ' '; for (int v : ebcc[i]) cout << v << ' '; cout << '\n'; } return 0; }
- 1
Information
- ID
- 415
- Time
- 2000~5000ms
- Memory
- 512MiB
- Difficulty
- 7
- Tags
- # Submissions
- 60
- Accepted
- 14
- Uploaded By