#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
vector<int> graph[1000005];
int n;
struct disj{
int pa[1000005];
int degcnt[1000005][5];
int repres[1000005];
int cnt[1000005];
int size[1000005];
bool trash[1000005];
bool bad[1000005];
bool cycle[1000005];
void init(int n){
for(int i=0; i<=n; i++) pa[i] = i, degcnt[i][0] = 1, size[i] = 1, repres[i] = -1;
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
void uni(int p, int q){
p = find(p); q = find(q);
if(p == q) return;
pa[q] = p; find(q);
for(int i=0; i<5; i++){
degcnt[p][i] += degcnt[q][i];
}
size[p] += size[q];
if(degcnt[p][4] > 1 || degcnt[p][3] > 4){
trash[p] = 1;
bad[p] = 0;
cycle[p] = 0;
return;
}
else{
repres[p] = max(repres[p], repres[q]);
}
if(degcnt[p][3] || degcnt[p][4]){
bad[p] = 1;
cycle[p] = 0;
}
else if(degcnt[p][1] == 0){
cycle[p] = 1;
}
}
}disj;
void Init(int N){
n = N;
disj.init(n);
}
int deg[1000005];
void Link(int A, int B){
graph[A].push_back(B);
graph[B].push_back(A);
deg[A]++, deg[B]++;
int p = disj.find(A);
if(deg[A] <= 4){
disj.degcnt[p][deg[A]-1]--;
disj.degcnt[p][deg[A]]++;
if(deg[A] == 3) disj.repres[p] = A;
}
p = disj.find(B);
if(deg[B] <= 4){
disj.degcnt[p][deg[B]-1]--;
disj.degcnt[p][deg[B]]++;
if(deg[B] == 3) disj.repres[p] = B;
}
disj.uni(A,B);
}
bool vis[1000005];
queue<int> q;
bool tvis[1000005];
int solve(int x){
memset(tvis,0,sizeof(tvis));
tvis[x] = 1;
int ret = 1;
for(auto &i : graph[x]){
deg[x]--;
deg[i]--;
}
for(auto &i : graph[x]){
if(tvis[i]) continue;
tvis[i] = 1;
q.push(i);
int foundThree = 0, foundOne = 0, foundTwo = 0;
while(!q.empty()){
int qf = q.front();
q.pop();
if(deg[qf] >= 3) foundThree = 1;
if(deg[qf] == 1) foundOne = 1;
if(deg[qf] == 2) foundTwo = 1;
for(auto &i : graph[qf]){
if(!tvis[i]){
tvis[i] = 1;
q.push(i);
}
}
}
ret &= (!foundThree && !(foundTwo && !foundOne));
}
for(auto &i : graph[x]){
deg[x]++;
deg[i]++;
}
return ret;
}
int CountCritical(){
memset(vis,0,sizeof(vis));
int ret = 0, pos = -1;
for(int i=0; i<n; i++){
int p = disj.find(i);
if(vis[p]) continue;
vis[p] = 1;
if(disj.trash[p]) return 0;
else if(disj.cycle[p]){
if(~pos) return 0;
pos = p;
ret = disj.size[p];
}
else if(disj.bad[p]){
if(~pos) return 0;
pos = p;
ret = -1;
}
else{
if(pos == -1) ret += disj.size[p];
}
}
if(ret == -1){
ret = 0;
pos = disj.repres[pos];
if(solve(pos)) ret++;
for(auto &k : graph[pos]){
if(solve(k)) ret++;
}
}
return ret;
}
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
void Init(int N);
int CountCritical();
void Link(int a, int b);
int main() {
int tmp;
/* Set input and output buffering */
char *inbuf, *outbuf;
inbuf = (char*) malloc(inbuf_len * sizeof(char));
outbuf = (char*) malloc(outbuf_len * sizeof(char));
tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
int N, L;
tmp = scanf("%d %d", &N, &L);
assert(tmp == 2);
Init(N);
int i;
for (i = 0; i < L; i++) {
int A, B;
tmp = scanf("%d", &A);
if (A == -1) {
int critical;
critical = CountCritical();
printf("%d\n", critical);
} else {
tmp = scanf("%d", &B);
assert(tmp == 1);
Link(A, B);
}
}
return 0;
}
Compilation message
/tmp/ccpayBTv.o: In function `main':
rings.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccodVcKU.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
