1 条题解

  • 0
    @ 2024-10-31 20:25:56

    AC代码:

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 5;
    int n, m, dfn[maxn], low[maxn], idx;
    struct Edge {
    	int v, id;
    };
    vector<Edge> g[maxn];
    bool cut[maxn*2];
    
    void tarjan(int u, int pe) {
    	dfn[u] = low[u] = ++idx;
    	for (auto e : g[u]) {
    		int v = e.v, id = e.id;
    		if (id == pe) continue;
    		if (!dfn[v]) {
    			tarjan(v, id);
    			low[u] = min(low[u], low[v]);
    		}
    		else low[u] = min(low[u], dfn[v]);
    	}
    	if (low[u] == dfn[u])
    		cut[pe] = true;
    }
    
    int main() {
    	scanf("%d%d", &n, &m);
    	for (int i = 1; i <= m; i++) {
    		int u, v;
    		scanf("%d%d", &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, 0);
    	int cnt = 0;
    	for (int i = 1; i <= m; i++)
    		cnt += cut[i];
    	printf("%d\n", cnt);
    	for (int i = 1; i <= m; i++)
    		if (cut[i])
    			printf("%d ", i);
    	return 0;
    }
    
    • 1

    信息

    ID
    69
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    3
    已通过
    3
    上传者