AC

许诺  •  7天前


#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAXN = 500005; const int MAXM = 4000005; // 注意重边,需要开两倍

struct Edge {

int to, next;
bool isBridge;

} edges[MAXM];

int head[MAXN], cnt = 1; // 从1开始,方便异或找反向边 int dfn[MAXN], low[MAXN], idx; stack stk; vector<vector> dcc; // 存储所有边双连通分量 bool inStack[MAXN]; int n, m;

void addEdge(int u, int v) {

edges[++cnt] = {v, head[u], false};
head[u] = cnt;

}

void tarjan(int u, int fromEdge) {

dfn[u] = low[u] = ++idx;
stk.push(u);
inStack[u] = true;

for (int i = head[u]; i; i = edges[i].next) {
    int v = edges[i].to;
    
    // 如果是反向边,跳过
    if (i == (fromEdge ^ 1)) continue;
    
    if (!dfn[v]) {
        tarjan(v, i);
        low[u] = min(low[u], low[v]);
        
        // 判断是否为桥
        if (low[v] > dfn[u]) {
            edges[i].isBridge = true;
            edges[i ^ 1].isBridge = true;
        }
    } else if (inStack[v]) {
        low[u] = min(low[u], dfn[v]);
    }
}

// 如果u是当前分量的根节点
if (low[u] == dfn[u]) {
    vector<int> component;
    while (true) {
        int v = stk.top();
        stk.pop();
        inStack[v] = false;
        component.push_back(v);
        if (v == u) break;
    }
    dcc.push_back(component);
}

}

int main() {

ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> m;

// 读入边
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    // 自环不需要添加两次
    if (u == v) {
        addEdge(u, v);
        addEdge(v, u);
    } else {
        addEdge(u, v);
        addEdge(v, u);
    }
}

// 对每个连通分量进行 Tarjan
for (int i = 1; i <= n; i++) {
    if (!dfn[i]) {
        tarjan(i, 0);
    }
}

// 输出结果
cout << dcc.size() << "\n";
for (auto& component : dcc) {
    cout << component.size();
    // 按题目要求排序输出(可选)
    sort(component.begin(), component.end());
    for (int node : component) {
        cout << " " << node;
    }
    cout << "\n";
}

return 0;

}


评论:

请先登录,才能进行评论