#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
i << '{' << j.size() << ':';
for (T ii : j) i << ' ' << ii;
return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
if (_split)
cerr << ", ";
cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
cerr << '[';
for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "Line(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << ']' << endl
#define debuga(i) cerr << "Line(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name()))
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;
vector<int> deg, rt, stk, ring;
vector<int> v;
vector<vector<int>> g;
vector<bool> vis;
bool fail;
int n, _count;
int find(int i) {
return rt[i] = rt[i] == i ? i : find(rt[i]);
}
void dfs(int i, int p) {
vis[i] = true;
stk.push_back(i);
for (int j : g[i])
if (j != p) {
if (!vis[j])
dfs(j, i);
else {
while (stk.back() != j)
ring.push_back(stk.back()), stk.pop_back();
ring.push_back(j);
return;
}
if (!ring.empty())
return;
}
stk.pop_back();
}
void upd(vector<int> tmp) {
if (fail)
return;
if (v.empty()) {
v = tmp;
return;
}
for (int i = 0; i < (int)v.size(); ) {
bool find = false;
for (int j : tmp)
if (v[i] == j) {
find = true;
}
if (!find)
swap(v[i], v.back()), v.pop_back();
else
++i;
}
if (v.empty())
fail = true;
}
void Init(int N) {
deg.assign(N, 0);
rt.resize(N);
iota(all(rt), 0);
vis.assign(N, false);
g.assign(N, vector<int>());
fail = false;
n = N;
}
void Link(int x, int y) {
if (fail)
return;
++deg[x], ++deg[y];
g[x].push_back(y), g[y].push_back(x);
if (deg[x] == 4) {
vector<int> tmp(1, x);
upd(tmp);
}
else if (deg[x] == 3) {
vector<int> tmp = g[x];
tmp.push_back(x);
upd(tmp);
}
if (fail)
return;
if (deg[y] == 4) {
vector<int> tmp(1, y);
upd(tmp);
}
else if (deg[y] == 3) {
vector<int> tmp = g[y];
tmp.push_back(y);
upd(tmp);
}
if (fail)
return;
if (find(x) == find(y)) {
if (_count < 30) {
++_count;
dfs(x, -1);
debug(ring);
upd(ring);
ring.clear();
stk.clear();
vis.assign(n, false);
}
else if (!v.empty() && find(v.back()) != find(x))
fail = true;
}
else {
rt[find(x)] = find(y);
}
}
int CountCritical() {
if (fail)
return 0;
if (v.empty())
return n;
return v.size();
}
signed main() {
Init(7);
pi a[]{{1, 2}, {0, 5}, {2, 0}, {3, 2}, {3, 5}, {4, 3}};
for (pi i : a)
cout << CountCritical() << endl, Link(i.first, i.second), debug(v);
cout << CountCritical() << endl;
}
Compilation message
/usr/bin/ld: /tmp/ccmgXTmb.o: in function `main':
rings.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccr4cF18.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
