#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define N 1000005
using namespace std;
#include "grader.h"
typedef long long ll;
typedef pair < int , int > ii;
int n, m, k, f, ata[5][N], kom[5][N],dur[5], ne[5], son[5], say, vis[N];
ii b[N];
vector < int > g[N];
int atabul(int d, int x){return ata[d][x] = (ata[d][x] != x) ? atabul(d, ata[d][x]) : x;}
bool bir(int d, int u, int v){
int xx = atabul(d, u);
int yy = atabul(d, v);
if(xx != yy){
if(rand()%2)
ata[d][xx] = yy;
else
ata[d][yy] = xx;
return 1;
}
return 0;
}
void Init(int nn){
srand(time(0));
n = nn;
for(int i = 1; i <= n; i++)
for(int j = 0; j < 5; j++)
ata[j][i] = i;
for(int i = 1; i <= 4; i++){
son[i] = dur[i] = 1;
}
dur[0] = n;
}
void dfs(int node){
say++;
vis[node] = 1;
for(int i = 0; i < g[node].size(); i++)
if(!vis[g[node][i]])
dfs(g[node][i]);
}
void Link(int u, int v){
u++;v++;
kom[0][u]++;
kom[0][v]++;
g[u].pb(v);
g[v].pb(u);
b[++m] = mp(u, v);
if(!f){
if(kom[0][u] == 3){
dur[0] = 0;
f = 1;
ne[++k] = u;
for(int i = 0; i < g[u].size(); i++)
ne[++k] = g[u][i];
} else if(kom[0][v] == 3){
dur[0] = 0;
f = 1;
ne[++k] = v;
for(int i = 0; i < g[v].size(); i++)
ne[++k] = g[v][i];
// cout << "Pat" << " " << ne[1] << " " << ne[2] << " " << ne[3] << " " << ne[4] << endl;
} else{
if(!bir(0, u, v)){
if(dur[0] != n)
dur[0] = 0;
else{
say = 0;
dfs(u);
dur[0] = say;
}
}
}
}
}
int CountCritical(){
if(!f)
return dur[0];
int ans = 0;
for(int i = 1; i <= 4; i++){
if(!dur[i])
continue;
for(;son[i] <= m; son[i]++){
int u = b[son[i]].st;
int v = b[son[i]].nd;
if(u == ne[i] or v == ne[i])
continue;
// cout << i << " " << u << " " << v << endl;
kom[i][u]++;
kom[i][v]++;
if(kom[i][u] == 3)
dur[i] = 0;
if(kom[i][v] == 3)
dur[i] = 0;
if(!bir(i, u, v))
dur[i] = 0;
}
ans += dur[i];
}
return ans;
}
// int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// Init(7);
// cout << CountCritical() << endl;
// Link(1, 2);
// cout << CountCritical() << endl;
// Link(0, 5);
// cout << CountCritical() << endl;
// Link(2, 0);
// cout << CountCritical() << endl;
// Link(3, 2);
// cout << CountCritical() << endl;
// Link(3, 5);
// cout << CountCritical() << endl;
// Link(4, 3);
// cout << CountCritical() << endl;
// return 0;
// }
Compilation message
rings.cpp:9:10: fatal error: grader.h: No such file or directory
#include "grader.h"
^~~~~~~~~~
compilation terminated.
