#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include "grader.h"
using namespace std;
int n, cycsz;
bool nne;
vector<int> adj[1000005];
vector<pair<int, int>> edges;
struct UnionFind1 {
int rt, par[1000005], deg[1000005];
bool vld;
int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
void merge(int x, int y) {
if (!vld || x == rt || y == rt) return;
if (deg[x] == 2 || deg[y] == 2 || same(x, y)) {
vld = false;
return;
}
deg[x]++;
deg[y]++;
par[find(x)] = find(y);
}
UnionFind1(int root) {
rt = root;
vld = true;
for (int i = 0; i < 1000005; i++) {
par[i] = i;
deg[i] = 0;
}
for (auto [a, b] : edges) {
merge(a, b);
}
}
};
struct UnionFind2 {
int par[1000005], sz[1000005];
UnionFind2() {
for (int i = 0; i < 1000005; i++) {
par[i] = i;
sz[i] = 1;
}
}
int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
sz[x] += sz[y];
par[y] = x;
return true;
}
} cyc;
vector<UnionFind1> uf;
void Init(int N) {
n = N;
}
int CountCritical() {
if (nne) return 0;
if (!uf.empty()) {
int ans = 0;
for (UnionFind1 u : uf) {
ans += u.vld;
}
return ans;
} else if (cycsz) return cycsz;
return n;
}
void Link(int a, int b) {
if (nne) return;
if (!uf.empty()) {
for (UnionFind1 u : uf) {
u.merge(a, b);
}
return;
}
edges.push_back({a, b});
adj[a].push_back(b);
adj[b].push_back(a);
if (adj[a].size() < adj[b].size()) swap(a, b);
if (adj[a].size() == 3) {
uf.push_back(UnionFind1(a));
for (int i : adj[a]) {
uf.push_back(UnionFind1(i));
}
return;
}
if (!cyc.merge(a, b)) {
if (cycsz) {
nne = true;
return;
}
cycsz = cyc.sz[cyc.find(a)];
}
}
Compilation message
rings.cpp:5:10: fatal error: grader.h: No such file or directory
5 | #include "grader.h"
| ^~~~~~~~~~
compilation terminated.
