#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
const int N = 1000000 + 5;
int n, sz = 0, h[N];
int cycle[7], rem[7], stop = 0, p[N][7];
set<pii> tried[6], deg;
vector<int> V[7][N];
void Init(int N_) {
n = N_;
for(int i = 0; i < n; i++) {
for(int t = 0; t < 6; t++) {
p[i][t] = i;
}
deg.insert({0, i});
}
}
int find(int a, int t) {
return (p[a][t] == a ? p[a][t] : p[a][t] = find(p[a][t], t));
}
void merge(int a,int b, int t) {
a = find(a, t); b = find(b, t);
if(a == b) return;
p[a][t] = b;
return;
}
void dfs(int a, int p) {
h[a] = h[p] + 1;
for(int i = 0; i < V[5][a].size(); i++) {
if(V[5][a][i] == p) continue;
if(sz) return;
if(h[V[5][a][i]]) {
sz = h[a] - h[V[5][a][i]] + 1;
return;
} else dfs(V[5][a][i], a);
}
}
void add(int a, int b, int t) {
if(a == rem[t] || b == rem[t]) return;
tried[t].erase({V[t][a].size(), a});
tried[t].erase({V[t][b].size(), b});
V[t][a].push_back(b); V[t][b].push_back(a);
tried[t].insert({V[t][a].size(), a});
tried[t].insert({V[t][b].size(), b});
if(find(a, t) == find(b, t)) cycle[t] = 1;
else merge(a, b, t);
return;
}
void Link(int a, int b) {
deg.erase({V[5][a].size(), a});
deg.erase({V[5][b].size(), b});
V[5][a].push_back(b); V[5][b].push_back(a);
deg.insert({V[5][a].size(), a});
deg.insert({V[5][b].size(), b});
if(find(a, 5) != find(b, 5)) {
merge(a, b, 5);
}
else {
if(!cycle[5]) {
merge(a, b, 5);
dfs(a, -1);
cycle[5] = a + 1;
}
else if(find(a, 5) != find(cycle[5] - 1, 5)) {
stop = 1;
}
}
if(tried[0].size()) {
add(a, b, 0);
}
if(tried[1].size()) {
for(int i = 1; i <= 4; i++) add(a, b, i);
}
}
void build(int t) {
int u = rem[t];
for(int i = 0; i < n; i++) {
if(u == i) continue;
for(int j = 0; j < V[5][i].size(); j++) {
int v = V[5][i][j];
if(v == u || v < i) continue;
if(find(v, t) == find(i, t)) cycle[t] = 1;
merge(i, v, t);
V[t][i].push_back(v); V[t][v].push_back(i);
}
}
for(int i = 0; i < n; i++) tried[t].insert({V[t][i].size(), i});
}
int CountCritical() {
if(stop) return 0;
if(!cycle[5] && (*--deg.end()).f <= 2) return n;
if((*--deg.end()).f <= 2) return sz;
if((*--deg.end()).f >= 4) {
if(!tried[0].size()) {
rem[0] = (*--deg.end()).s;
build(0);
}
if((*--tried[0].end()).f <= 2 && !cycle[0]) return 1;
stop = 1;
return 0;
}
if(!tried[1].size()) {
rem[1] = (*--deg.end()).s;
for(int i = 0; i < V[5][rem[1]].size(); i++) {
rem[i + 2] = V[5][rem[1]][i];
}
for(int i = 1; i <= 4; i++) {
build(i);
}
}
int cn = 0;
for(int i = 1; i <= 4; i++) {
if((*--tried[i].end()).f <= 2 && !cycle[i]) cn++;
}
return cn;
}
int main() {
int n; cin >> n;
Init(n);
while(true) {
int t, x;
cin >> t;
if(t == 0) {
cout << CountCritical() << "_______________" << endl;
// system("pause");
continue;
}
int u,v; cin >> u >> v;
Link(u, v);
}
}
Compilation message
rings.cpp: In function 'void dfs(int, int)':
rings.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < V[5][a].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'void build(int)':
rings.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int j = 0; j < V[5][i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int i = 0; i < V[5][rem[1]].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
rings.cpp: In function 'int main()':
rings.cpp:127:10: warning: unused variable 'x' [-Wunused-variable]
127 | int t, x;
| ^
/usr/bin/ld: /tmp/cchrekl1.o: in function `main':
rings.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccCjoCU1.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
