#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;
struct UnionFind{
bool good = 1;
int root;
vector<int> pai, degree;
UnionFind(int n = 0, int start = 0){
root = start;
pai = vector<int>(n+1);
iota(all(pai),0);
degree = vector<int>(n+1);
}
int find (int id){
if(pai[id] == id)
return id;
return pai[id] = find(pai[id]);
}
void onion(int a, int b){
if(a == root || b == root)
return;
//cout << root << " push(" << a << ',' << b << ")\n";
degree[a]++;
degree[b]++;
if(degree[a] == 3)
good = 0;//, cout << "=>" << root << " bad " << a << "\n";
if(degree[b] == 3)
good = 0;//, cout << "=>" << root << " bad " << b << "\n";
a = find(a), b = find(b);
if(a!=b){
pai[b] = a;
} else {
good = 0;//, cout << "=>" << root << " badc\n";
}
}
};
struct UnionFind2{
int cycle = -1;
int cyclect = 0;
vector<int> pai, sizee;
UnionFind2(int n = 0){
pai = vector<int>(n+1);
sizee = vector<int> (n+1,1);
iota(all(pai),0);
}
int find (int id){
if(pai[id] == id)
return id;
return pai[id] = find(pai[id]);
}
void onion(int a, int b){
a = find(a), b = find(b);
if(a == b){
cycle = a;
cyclect++;
} else{
sizee[a] += sizee[b];
pai[b] = a;
}
}
} ufsmall;
int n;
matrix<int> g;
vector<UnionFind> uf;
int mode = 0;
void inituf(int x, int y){
for(int i : g[x]){
uf.push_back(UnionFind(n,i));
for(int j = 0; j < n; j++){
for(int k : g[j]){
if(j > k)
continue;
int a = j , b = k;
if(!(a == min(x,y) && b == max(x,y)))
uf.back().onion(j,k);
}
}
}
cand[x] = uf.size();
uf.push_back(UnionFind(n,x));
for(int j = 0; j < n; j++){
for(int k : g[j]){
if(j > k)
continue;
int a = j , b = k;
if(!(a == min(x,y) && b == max(x,y)))
uf.back().onion(j,k);
}
}
}
void Init(int N_) {
n = N_;
g = matrix<int>(n+1);
cand = vector<int>(n+1,-1);
ufsmall = UnionFind2(n);
}
void Link(int A, int B) {
if(mode == 3)
return;
g[A].push_back(B);
g[B].push_back(A);
if(g[A].size() == 3 && mode == 0){
mode = 1;
inituf(A,B);
}
if(g[B].size() == 3 && mode == 0){
mode = 1;
inituf(B,A);
}
if(mode == 0){
ufsmall.onion(A,B);
if(ufsmall.cyclect >= 2)
mode = 3;
}
for(auto& i : uf){
i.onion(A,B);
}
}
int CountCritical() {
if(mode == 3)
return 0;
if(mode == 0){
if(ufsmall.cyclect == 0)
return n;
return ufsmall.sizee[ufsmall.cycle];
}
int resp =0;
for(auto& i : uf){
//cout << "->" << i.root << ' ' << i.good << '\n';
resp+=i.good;
}
return resp;
}
Compilation message
rings.cpp: In function 'void inituf(int, int)':
rings.cpp:105:5: error: 'cand' was not declared in this scope; did you mean 'rand'?
105 | cand[x] = uf.size();
| ^~~~
| rand
rings.cpp: In function 'void Init(int)':
rings.cpp:124:3: error: 'cand' was not declared in this scope; did you mean 'rand'?
124 | cand = vector<int>(n+1,-1);
| ^~~~
| rand
