#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#define pb push_back
#define All(x) x.begin(), x.end()
using namespace std;
#define debug(args) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
int N;
vector <int> dsu; // DSU
vector <int> sze; // SIZE of DSU
vector <int> deg; // degree
vector < vector<int> > path;
vector <int> nowCritical; // now answer
void Init(int n) {
N = n;
nowCritical.clear();
dsu.clear(), dsu.resize(N);
sze.clear(), sze.resize(N);
deg.clear(), deg.resize(N);
path.clear(), path.resize(N);
for (int i = 0; i < N; i++) {
dsu[i] = i;
nowCritical.pb(i);
}
}
int fnd(int a) {
return dsu[a] == a ? dsu[a] : dsu[a] = fnd(dsu[a]);
}
inline void Union(int a, int b) {
a = fnd(a), b = fnd(b);
if (sze[a] > sze[b]) {
sze[a] += sze[b];
dsu[b] = a;
} else {
sze[b] += sze[a];
dsu[a] = b;
}
}
inline void Only(int v) {
bool flag = 0;
for (int i : nowCritical)
if (i == v) flag = 1;
nowCritical.clear();
if (flag) nowCritical.pb(v);
return;
}
inline void Left(int v) {
vector <int> tmp;
for (int j : nowCritical) {
for (int i = 0; i < 3; i++)
if (j == path[v][i]) tmp.pb(j);
if (j == v) tmp.pb(v);
}
nowCritical = tmp;
return;
}
inline bool del(int id, int a, int b) {
if (id == a || id == b) return 1;
vector <bool> vis(N);
queue <int> nxt;
nxt.push(a), vis[a] = 1;
while (nxt.size() && !vis[b]) {
int now = nxt.front();
nxt.pop();
for (int i : path[now]) {
if (vis[i] || i == id) continue;
vis[i] = 1, nxt.push(i);
}
}
return !vis[b];
}
inline void check(int s, int t) {
vector <int> tmp;
for (int i : nowCritical)
if (fnd(i) == fnd(s))
tmp.pb(i);
nowCritical = tmp;
return;
}
void BFS(int s, int t) {
queue <int> nxt;
vector <bool> vis(N);
vector <int> pre(N, -1);
nxt.push(s), vis[s] = 1;
while (!vis[t]) {
int now = nxt.front();
nxt.pop();
for (int i : path[now]) {
if (vis[i]) continue;
vis[i] = 1, pre[i] = now;
nxt.push(i);
}
}
vector <int> cyc;
cyc.pb(t);
while (pre[t] != -1) {
cyc.pb(pre[t]);
t = pre[t];
}
vector <int> tmp;
for (int i : cyc)
for (int j : nowCritical)
if (i == j) tmp.pb(j);
nowCritical = tmp;
}
void Link(int a, int b) {
if (!nowCritical.size()) return;
deg[a]++;
if (deg[a] > 3) Only(a);
deg[b]++;
if (deg[b] > 3) Only(b);
if (fnd(a) != fnd(b)) {
Union(a, b);
} else if (nowCritical.size()) {
check(a, b);
BFS(s, t);
}
path[a].pb(b);
if (deg[a] == 3) Left(a);
path[b].pb(a);
if (deg[b] == 3) Left(b);
return;
}
int CountCritical() {
return nowCritical.size();
}
Compilation message
rings.cpp:2: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
2 | #pragma gcc optimize("O3")
|
rings.cpp: In function 'void Link(int, int)':
rings.cpp:128:9: error: 's' was not declared in this scope
128 | BFS(s, t);
| ^
rings.cpp:128:12: error: 't' was not declared in this scope
128 | BFS(s, t);
| ^
