【题解】CF-962E-Simple Cycles Edges

题目

http://codeforces.com/contest/962/problem/F

https://www.luogu.org/problemnew/show/CF962F

题意

问一个简单无向图,求出所有只出现在一个简单环上的边。

题解

  • Tarjan 求点双判断边数和点数是否相等

代码(模板 GET)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 2E5 + 100;
struct E { int to, nxt; } e[N];
int hd[N], ecnt;
void addedge(int u, int v) {
e[ecnt] = {v, hd[u]};
hd[u] = ecnt++;
}
int low[N], dfn[N], clk, B, bno[N];
vector<int> bc[N], be[N];
bool vise[N];
void init() {
memset(vise, 0, sizeof vise);
memset(hd, -1, sizeof hd);
memset(dfn, 0, sizeof dfn);
memset(bno, -1, sizeof bno);
B = clk = 0;
}

void tarjan(int u, int feid) {
static int st[N], p;
static auto add = [&](int x) {
if (bno[x] != B) { bno[x] = B; bc[B].push_back(x); }
};
low[u] = dfn[u] = ++clk;
for (int i = hd[u]; ~i; i = e[i].nxt) {
if ((feid ^ i) == 1) continue;
if (!vise[i]) { st[p++] = i; vise[i] = vise[i ^ 1] = true; }
int v = e[i].to;
if (!dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
bc[B].clear(); be[B].clear();
while (1) {
int eid = st[--p];
add(e[eid].to); add(e[eid ^ 1].to);
be[B].push_back(eid);
if ((eid ^ i) <= 1) break;
}
++B;
}
} else low[u] = min(low[u], dfn[v]);
}
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
init();
int n, m; cin >> n >> m;
FOR (_, 0, m) {
int u, v; scanf("%d%d", &u, &v);
addedge(u, v); addedge(v, u);
}
FOR (i, 1, n + 1) if (!dfn[i]) tarjan(i, -1);
vector<int> ans;
FOR (i, 0, B) {
if (be[i].size() == bc[i].size())
for (int& x: be[i]) ans.push_back(x / 2 + 1);
}
sort(ans.begin(), ans.end());
cout << ans.size() << endl;
FOR (i, 0, ans.size()) printf("%d%c", ans[i], i == _i - 1 ? '\n' : ' ');
}
w