#include<bits/stdc++.h>
using namespace std;
int n,cycle_size,cycles;
vector<int> adj[1000001];
bool flag = 1;
int sz[1000001],SZ[1000001], P[1000001] , ans, center = -1,help,seen[1000001],good;
bool bad[1000001];
set<int> more_than4;
int par(int a) {
if (a != P[a])
return P[a] = par(P[a]);
return a;
}
void join(int a,int b) {
int x = par(a);
int y = par(b);
if (x == y) return;
if (SZ[x] > SZ[y]) swap(x,y);
P[x] = y;
SZ[y] += SZ[x];
}
void Init(int N) {
ans = n = N;
for (int i = 0 ; i < n; i++)
P[i] = i,good[i] = SZ[i] = 1;
}
int vis[1000001];
void dfs (int v,int p,int X) {
if (sz[v] >= 3)
flag = 0;
vis[v] = help;
for (int i: adj[v]) {
if (i == p || i == X) continue;
if (vis[i] == help) {
flag = 0;
}else dfs(i,v,X);
}
}
bool check(int v) {
if (good[v] == 0) return 0;
help++;
flag = 1;
for (int i : adj[v]) sz[i]--;
for (int i = 0; i < n; i++)
if (i != v && help != vis[i]) dfs(i,-1,v);
for (int i : adj[v]) sz[i]++;
good[v] = flag;
return flag;
}
vector<int> dangerous;
void add(int x) {
if (bad[x]) return;
bad[x] = 1; dangerous.push_back(x);
}
void Link(int A, int B) {
if (ans == 0) return;
sz[A]++;
sz[B]++;
adj[A].push_back(B);
adj[B].push_back(A);
if (sz[A] == 3) {add(A);for (int i:adj[A]) add(i);}
if (sz[B] == 3) { add(B);for (int i : adj[B]) add(i);}
if (sz[A] >= 4) more_than4.insert(A);
if (sz[B] >= 4) more_than4.insert(B);
if (more_than4.size() >= 2) { ans = 0; return; }
if (A == center || B == center ) return;
int x = par(A), y = par(B);
join(A,B);
if (x != y && sz[A] <= 2 && sz[B] <= 2 ) return;
if (more_than4.size()) center = *more_than4.begin();
if (A == center) { ans = check(A); return;}
if (B == center) { ans = check(B); return;}
if (sz[A]>= 3 || sz[B] >= 3) {
int t = 0;
for (int j : dangerous) t += check(j);
ans = t;
return;
}
if (sz[A] == 1 || sz[B] == 1) return;
if (x == y && sz[A] == 2 && sz[B] == 2) {
if (dangerous.empty()) {
cycles++;
cycle_size = SZ[par(A)];
if (cycles > 1) { ans = 0; return;}
ans = cycle_size;
return ;
} else {
int t = 0;
if (center != -1 ){
ans = check(center);
return;
}
for (int j : dangerous) t += check(j);
ans = t;
return;
}
}
}
int CountCritical() {
return ans;
}
Compilation message
rings.cpp: In function 'void Init(int)':
rings.cpp:26:18: error: invalid types 'int[int]' for array subscript
P[i] = i,good[i] = SZ[i] = 1;
^
rings.cpp: In function 'bool check(int)':
rings.cpp:43:12: error: invalid types 'int[int]' for array subscript
if (good[v] == 0) return 0;
^
rings.cpp:50:8: error: invalid types 'int[int]' for array subscript
good[v] = flag;
^
