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;
}