#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
typedef long long ll;
using namespace std;
namespace std {
template <typename T, int D>
struct _vector : public vector <_vector <T, D - 1>> {
static_assert(D >= 1, "Dimension must be positive!");
template <typename... Args>
_vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
};
// _vector <int, 3> a(n, m, k);: int a[n][m][k].
// _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
template <typename T>
struct _vector <T, 1> : public vector <T> {
_vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
};
}
const int MAX = 1e6 + 3;
const ll MOD[] = {1000000007, 998244353};
int n, q;
bool badGraph; // no solulu for this graph
vector <int> adj[MAX];
vector <pair <int, int>> curEg;
int circleSize;
struct graph_t { // graph G after deleting vertex "deleted"
bool valid; // checking whether graph G is perfect or not
int deleted; // vertex we deleted from the graph
int deg[MAX], pa[MAX];
int findpa(int u) {
return u == pa[u] ? u : pa[u] = findpa(pa[u]);
}
void join(int u, int v) {
deg[u]++;
deg[v]++;
u = findpa(u);
v = findpa(v);
pa[v] = u;
}
void addEg(int u, int v) {
if (u == deleted || v == deleted || !valid) return;
if (deg[u] == 2 || deg[v] == 2 || findpa(u) == findpa(v)) return void(valid = 0); // graph must not contain cycle or with deg >= 3
join(u, v);
}
graph_t(int chosen) {
valid = 1;
deleted = chosen;
iota(pa + 1, pa + n + 1, 1);
fill(deg + 1, deg + n + 1, 0);
for (auto &[u, v] : curEg) addEg(u, v);
}
};
int pa[MAX], sz[MAX];
vector <graph_t> subGraphs;
int findpa(int u) {
return u == pa[u] ? u : pa[u] = findpa(pa[u]);
}
bool join(int u, int v) {
u = findpa(u);
v = findpa(v);
if (u != v) {
pa[v] = u;
sz[u] += sz[v];
return 1;
}
return 0;
}
void Link(int u, int v) {
if (badGraph) return;
if (subGraphs.size()) for (auto &G : subGraphs) G.addEg(u, v);
else {
if (adj[u].size() < adj[v].size()) swap(u, v);
curEg.push_back(make_pair(u, v));
adj[u].push_back(v);
adj[v].push_back(u);
if ((int)adj[u].size() == 3) { // if there's an vertex with deg >= 3, then the answer must be itself or its adjacent vertex
// We create some subGraphs
subGraphs.push_back(graph_t(u));
for (int &v : adj[u]) subGraphs.push_back(graph_t(v));
} else {
if (!join(u, v)) {
if (circleSize != 0) badGraph = 1;
else circleSize = sz[findpa(u)];
}
}
}
}
int countCritical() {
if (badGraph) return 0;
if (subGraphs.size()) {
int res = 0;
for (auto &G : subGraphs) res += G.valid;
return res;
}
if (circleSize) return circleSize;
return n;
}
void Init(int _n) {
n = _n;
}
Compilation message
/usr/bin/ld: /tmp/ccVtKLpm.o: in function `main':
grader.cpp:(.text.startup+0xed): undefined reference to `CountCritical()'
collect2: error: ld returned 1 exit status
