1 solutions

  • 1
    @ 2025-7-4 14:55:30

    想说一下处理重边的一种方法:给边加编号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