#include<cstdio>
#include<vector>
#include<set>
using namespace std;
const int SZ = 100010;
int min(int a, int b) { return a < b ? a : b; }
int n;
const bool ifDebug = false;
int cycleNum;
typedef struct Graph {
vector<vector<int>>l, cs;
int st[5], ts[3];
vector<int>p, sz;
int x;
void init() {
x = n;
l.resize(n);
p.resize(n);
sz.resize(n);
cs.resize(n);
st[0] = ts[0] = n;
st[1] = st[2] = st[3] = st[4] = ts[1] = ts[2] = 0;
for (int i = 0; i < n; i++) {
p[i] = i;
cs[i].resize(5);
cs[i][0] = sz[i] = 1;
}
}
void init(int X, Graph* G) {
init();
x = X;
for (int i = 0; i < n; i++) {
for (int e : (*G).l[i]) {
if (e < i)Link(e, i);
}
}
}
int f(int a) {
vector<int>v;
while (a != p[a]) {
v.push_back(a);
a = p[a];
}
for (int e : v)p[e] = a;
return a;
}
void u(int A, int B) {
int a = f(A), b = f(B);
if (a != b) {
p[b] = a;
ts[gT(a)]--;
ts[gT(b)]--;
for (int i = 0; i < 5; i++) {
cs[a][i] += cs[b][i];
}
sz[a] += sz[b];
}
else {
ts[gT(a)]--;
}
}
void Con(int A, int B) {
int a = f(A);
cs[a][min(l[A].size(), 4)]--;
st[min(l[A].size(), 4)]--;
l[A].push_back(B);
cs[a][min(l[A].size(), 4)]++;
st[min(l[A].size(), 4)]++;
}
int gT(int a) {
if (cs[a][4] + cs[a][3]) {
return 2;
}
else if (cs[a][2] && (cs[a][1] + cs[a][0] == 0)) {
return 1;
}
else {
return 0;
}
}
void Link(int A, int B) {
if (A == x || B == x)return;
u(A, B);
Con(A, B);
Con(B, A);
int a = f(A);
ts[gT(a)]++;
}
bool isChain() {
return (ts[1] + ts[2] == 0);
}
void PR() {
if (!ifDebug)return;
printf("-------%d-------\n", x);
for (int a = 0; a < n; a++) {
if (a == p[a]) {
printf("[%d(%d,%d)]", a, sz[a], gT(a));
for (int b = 0; b < 5; b++)printf(" %d", cs[a][b]);
printf("\n");
}
else {
printf("%d->%d\n", a, f(a));
}
}
printf("-----------------\n");
}
}Graph;
Graph MG, GV[4];
int GS;
//type: 0-chain/1-cycle/2-3 exists/3-4 exists
void Init(int N) {
cycleNum = n = N;
MG.init();
}
void Link(int A, int B) {
bool p = (MG.st[3] + MG.st[4] == 0);
MG.Link(A, B);
for (int i = 0; i < GS; i++) {
GV[i].Link(A, B);
}
if (MG.sz[MG.f(A)])cycleNum = MG.f(A);
if (MG.sz[MG.f(A)])cycleNum = MG.f(B);
if (p && MG.st[3]) {
if (ifDebug)printf("걸렸구나!!!!!!!!!\n");
int a = A;
if (MG.l[A].size() < 3)a = B;
GV[GS++].init(a, &MG);
//return;
for (int e : MG.l[a]) {
GV[GS++].init(e, &MG);
}
}
}
int CountCritical() {
if (MG.ts[2]) {
if (ifDebug)printf(">=3 Exists");
int r = 0;
for (int i = 0; i < GS; i++) {
if (GV[i].isChain())r++;
}
return r;
}
else if (MG.ts[1]) {
if (ifDebug)printf("cycle Exists");
if (MG.ts[1] > 1)return 0;
return MG.sz[cycleNum];
}
else {
if (ifDebug)printf("Already Chain");
return n;
}
}
int main() {
int n, l, a, b;
scanf("%d%d", &n, &l);
init(n);
while (l--) {
scanf("%d", &a);
if (a == -1) {
printf("%d\n", CountCritical());
}
else {
scanf("%d", &b);
Link(a, b);
}
MG.PR();
for (a = 0; a < GS; a++) {
GV[a].PR();
}
}
return 0;
}
Compilation message
rings.cpp: In function 'int main()':
rings.cpp:156:2: error: 'init' was not declared in this scope; did you mean 'Init'?
156 | init(n);
| ^~~~
| Init
rings.cpp:155:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
155 | scanf("%d%d", &n, &l);
| ~~~~~^~~~~~~~~~~~~~~~
rings.cpp:158:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | scanf("%d", &a);
| ~~~~~^~~~~~~~~~
rings.cpp:163:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
163 | scanf("%d", &b);
| ~~~~~^~~~~~~~~~
