有關無向圖的問題

CF 962F  點選打開連結

求一個無向圖中所有的出現且僅出現在一個環中的邊。 先求出雙聯通分量，一個雙聯通分量從直覺上來看就是若幹個圈并在一起，而且圈與圈之間是通過邊來相交的。自己畫圖感受一下，顯然若一個雙聯通分量就是一個簡單環（也就是說點數等于邊數），那麼該雙聯通分量的邊全是符合要求的，否則這些邊就全部不符合要求。

#include <vector>
#include <cstdio>
#include <cstring>
#include <map>
#include <stack>
#include <algorithm>
#include <iostream>
#define N 110000
using namespace std;
vector<int> g[N], q[N], ans;
map<int, int> p;
struct edge
{
	int x, y;
};
stack<edge> s;
int n, m, x, y, pre[N], low[N], tot, num, bcc[N], sumx[N], sume[N];

int dfs(int x, int fa)
{
	int lowx = pre[x] = ++ tot;
	int child = 0;
	for(int i = 0; i < g[x].size(); i ++)
	{
		int y = g[x][i];
		edge e = (edge){x, y};
		if (!pre[y])
		{
			s.push(e);
			child ++;
			int lowy = dfs(y, x);
			lowx = min(lowx, lowy);
			if (lowy >= pre[x])
			{
				num ++;
				while(true)
				{
					edge t = s.top(); s.pop();
					if (bcc[t.x] != num) {bcc[t.x] = num; sumx[num] ++;}
					if (bcc[t.y] != num) {bcc[t.y] = num; sumx[num] ++;}
					sume[num] ++;
					q[num].push_back((t.x - 1) * n + t.y);
					if (t.x == x && t.y == y) break;
				}
			}
		}
		else if (pre[y] < pre[x] && y != fa)
		{
			s.push(e);
			lowx = min(lowx, pre[y]);
		}
	}
	return lowx;
}

int main()
{
	freopen("1.in", "r", stdin);
	freopen("1.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++)
	{
		scanf("%d%d", &x, &y);
		g[x].push_back(y);
		g[y].push_back(x);
		p[(x - 1) * n + y] = i;
		p[(y - 1) * n + x] = i;
	}
	for(int i = 1; i <= n; i ++)
		if (!pre[i]) dfs(i, -1);
	for(int i = 1; i <= num; i ++)
		if (sumx[i] == sume[i])
			for(int j = 0; j < q[i].size(); j ++)
				ans.push_back(p[q[i][j]]);
	sort(ans.begin(), ans.end());
	cout << ans.size() << endl;
	for(int i = 0; i < ans.size(); i ++) printf("%d ", ans[i]);
	return 0;
}