#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
vector<pair<int, int> > con;
vector<int> adj[1000005];
set<int> pos, t;
int N;
int p[1000005][3];
void Init(int N_) {
N = N_;
for(int i = 0; i < N; i++)
for(int j = 0; j < 3; j++)
p[i][j] = i;
for(int i = 0; i < N; i++)
pos.insert(i);
}
int put = 0;
int v[3];
int find(int v, int i){
if(v == p[v][i]) return v;
return p[v][i] = find(p[v][i], i);
}
bool merge(int v, int u, int i){
if(i){
if(v == ::v[i]) return 0;
if(u == ::v[i]) return 0;
}
v = find(v, i);
u = find(u, i);
if(v == u) return 1;
p[v][i] = u;
return 0;
}
bool dfs(int A, int B){
t.insert(A);
for(int x : adj[A]){
if(x == B) continue;
if(t.count(x)) return 1;
if(dfs(x, A)) return 1;
}
t.erase(A);
return 0;
}
void Link(int A, int B){
if(pos.empty()) return;
adj[A].push_back(B);
adj[B].push_back(A);
t.clear();
if(adj[A].size() == 4){
if(pos.count(A))
t.insert(A);
swap(t, pos);
t.clear();
} else if(adj[A].size() == 3){
if(pos.count(A))
t.insert(A);
for(int x : adj[A])
if(pos.count(x))
t.insert(x);
swap(t, pos);
t.clear();
}
if(adj[B].size() == 4){
if(pos.count(B))
t.insert(B);
swap(t, pos);
t.clear();
} else if(adj[B].size() == 3){
if(pos.count(B))
t.insert(B);
for(int x : adj[B])
if(pos.count(x))
t.insert(x);
swap(t, pos);
t.clear();
}
if(put == 0 && pos.size() <= 2){
for(int x : pos){
v[put++] = x;
}
for(auto x : con){
if(merge(x.ff, x.ss, 1)) v[1] = -1;
if(merge(x.ff, x.ss, 2)) v[2] = -1;
}
}
con.push_back({A, B});
if(put){
t.clear();
if(merge(A, B, 1)) v[1] = -1;
if(merge(A, B, 2)) v[2] = -1;
if(pos.count(v[1])) t.insert(v[1]);
if(pos.count(v[2])) t.insert(v[2]);
swap(t ,pos);
t.clear();
return;
}
if(pos.empty()) return;
if(merge(A, B, 0) == 0 || put) return;
dfs(A, B);
set<int> lol;
for(int x : t)
if(pos.count(x))
lol.insert(x);
swap(lol, pos);
t.clear();
}
int CountCritical() {
return pos.size();
}
#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;
int N, L;
scanf("%d %d", &N, &L);
Init(N);
int i;
for (i = 0; i < L; i++) {
int A, B;
scanf("%d", &A);
if (A == -1) {
int critical;
critical = CountCritical();
printf("%d\n", critical);
} else {
tmp = scanf("%d", &B);
Link(A, B);
}
}
return 0;
}
Compilation message
rings.cpp: In function 'void Init(int)':
rings.cpp:13:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i = 0; i < N; i++)
^~~
rings.cpp:16:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int i = 0; i < N; i++)
^~~
rings.cpp: In function 'int main()':
rings.cpp:127:7: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
int tmp;
^~~
rings.cpp:130:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &L);
~~~~~^~~~~~~~~~~~~~~~~
rings.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A);
~~~~~^~~~~~~~~~
/tmp/ccQfIrlS.o: In function `main':
rings.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc4tCUFS.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
