#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1000005], vis;
int n, p[1000005], s[1000005];
bool f = 1, timer = 0;
int find(int x) {
if (p[x] == x) {
return x;
}
p[x] = find(p[x]);
return p[x];
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return;
}
if (s[b] > s[a]) {
swap(a, b);
}
s[a] += s[b];
p[b] = a;
}
set<int> st;
void Init(int N_) {
n = N_;
for (int i = 0; i < n; i++) {
st.insert(i);
p[i] = i;
s[i] = 1;
}
}
void dfs(int i, int p, int s) {
if (vis[i] == timer) {
f = 0;
return;
}
vis[i] = timer;
for (int j : adj[i]) {
if (j == p || j == s) {
continue;
}
dfs(j, i, s);
}
}
int calc(int a) {
timer++;
vector<int> co(n, 0);
for (int j : adj[a]) {
co[j]++;
}
f = 1;
for (int i = 0; i < n; i++) {
if (i != a && adj[i].size()-co[i] > 2) {
f = 0;
break;
}
if (vis[i] == timer || i == a) {
continue;
}
dfs(i, -1, a);
}
return f;
}
int le = -1, pre[1000005];
void dfscyc(int i, int p) {
if (le != -1) {
return;
}
if (vis[i] == timer) {
set<int> b;
pre[i] = p;
int a = i;
le = 0;
a = pre[a];
if (st.count(a)) {
if (calc(a)) {
b.insert(a);
}
}
while(a != i) {
a = pre[a];
if (st.count(a)) {
if (calc(a)) {
b.insert(a);
}
}
}
st = b;
return;
}
vis[i] = timer;
pre[i] = p;
for (int j : adj[i]) {
if (j == p) {
continue;
}
dfscyc(j, i);
}
}
void cycle(int a) {
timer++;
le = -1;
dfscyc(a, 0);
}
bool cyc = 1, cant = 0;
int s4 = -1;
void Link(int A, int B) {
adj[A].push_back(B);
adj[B].push_back(A);
if (cant || st.size() == 0) {
return;
}
if (find(A) == find(B)) {
cycle(A);
}
if (find(A) != find(B)) {
merge(A, B);
}
if (adj[A].size() >= 4 && s4 == -1) {
cyc = 0;
s4 = A;
if (st.count(A) && calc(A)) {
st = {A};
} else {
st = {};
}
}
if (adj[B].size() >= 4 && s4 == -1) {
cyc = 0;
s4 = B;
if (st.count(B) && calc(B)) {
st = {B};
} else {
st = {};
}
}
if (adj[A].size() >= 4 && s4 != -1 && s4 != A) {
st.clear();
cant = 1;
return;
}
if (adj[B].size() >= 4 && s4 != -1 && s4 != B) {
st.clear();
cant = 1;
return;
}
if (adj[A].size() == 3) {
set<int> b;
if (st.count(A)) {
if (calc(A)) {
b.insert(A);
}
}
for (int j : adj[A]) {
if (st.count(j)) {
if (calc(j)) {
b.insert(j);
}
}
}
st = b;
}
if (adj[B].size() == 3) {
set<int> b;
if (st.count(B)) {
if (calc(B)) {
b.insert(B);
}
}
for (int j : adj[B]) {
if (st.count(j)) {
if (calc(j)) {
b.insert(j);
}
}
}
st = b;
}
}
int CountCritical() {
return st.size();
}
Compilation message
rings.cpp: In function 'int calc(int)':
rings.cpp:48:5: error: use of an operand of type 'bool' in 'operator++' is forbidden in C++17
48 | timer++;
| ^~~~~
rings.cpp: In function 'void cycle(int)':
rings.cpp:103:5: error: use of an operand of type 'bool' in 'operator++' is forbidden in C++17
103 | timer++;
| ^~~~~
