#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define ll long long
#define int long long
const long long inf=1e18;
const int MOD=998244353;
const int N=1e6+5;
vector<int> adj[N];
int n;
bool vis[N];
struct info{
int one;
int two;
int three;
int mx;
friend info operator+ (info a,info b){
a.one+=b.one;
a.two+=b.two;
a.three+=b.three;
a.mx=max(a.mx,b.mx);
}
};
info dfs(int node,int par){
vis[node]=1;
info rt; rt.one=0; rt.two=0; rt.three=0; rt.mx=adj[node].size();
if(adj[node].size()<=1)rt.one=1;
if(adj[node].size()==2)rt.two=1;
if(adj[node].size()==3)rt.three=1;
for(auto i:adj[node]){
if(vis[i])continue;
info s=dfs(i,node);
rt.one+=s.one;
rt.two+=s.two;
rt.three+=s.three;
rt.mx=max(rt.mx,s.mx);
}
return rt;
}
void dfs2(int node,int par){
vis[node]=1;
for(auto i:adj[node]){
if(!vis[i])dfs2(i,node);
}
}
void Init(int N){
}
void Link(int A, int B){
adj[A].pb(B);
adj[B].pb(A);
}
int CountCritical(){
for(int i=1;i<=n;i++)vis[i]=0;
info am; am.one=0; am.two=0; am.three=0; am.mx=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
info you=dfs(i,0);
if(you.mx==0)you.one++;
am.one+=you.one;
am.two+=you.two;
am.three+=you.three;
am.mx=max(am.mx,you.mx);
}
}
//cout<<am.mx<<" "<<am.one<<" "<<am.two<<" "<<am.three<<endl;
if(am.mx>3)return 0;
int ans=0;
for(int i=1;i<=n;i++){
// cout<<am.mx<<" "<<am.one<<" "<<am.two<<" "<<am.three<<endl;
info ar=am;
for(auto j:adj[i]){
if(adj[j].size()==3){
ar.three--;
ar.two++;
}
else if(adj[j].size()==2){
ar.two--;
ar.one++;
}
else{
ar.one++;
}
}
if(adj[i].size()==0)ar.one-=2;
if(adj[i].size()==1)ar.one--;
if(adj[i].size()==2)ar.two--;
if(adj[i].size()==3) ar.three--;
int comp=0;
for(int j=1;j<=n;j++)vis[j]=0;
vis[i]=1;
for(int j=1;j<=n;j++){
if(!vis[j]){
dfs2(j,0);
comp++;
}
}
// if(i==4)cout<<am.mx<<" "<<am.one<<" "<<am.two<<" "<<am.three<<' '<<comp<<endl;
bool flag=1;
if(ar.three>0)flag=0;
if(ar.one!=comp*2)flag=0;
if(flag)ans++;
}
return ans;
}
/*signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
/*
7 13
1 2
0 5
2 0
3 2
-1
3 5
-1
int l; cin>>n>>l;
Init(n);
for(int i=0;i<l;i++){
int x; cin>>x;
if(x==-1)cout<<CountCritical()<<endl;
else{
int b; cin>>b; x++; b++;
Link(x,b);
}
}
}*/
Compilation message
rings.cpp:110:5: warning: "/*" within comment [-Wcomment]
110 | /*
|
rings.cpp: In function 'info operator+(info, info)':
rings.cpp:23:5: warning: no return statement in function returning non-void [-Wreturn-type]
23 | }
| ^
/usr/bin/ld: /tmp/ccem0EP6.o: in function `main':
grader.cpp:(.text.startup+0x88): undefined reference to `Init(int)'
/usr/bin/ld: grader.cpp:(.text.startup+0xca): undefined reference to `Link(int, int)'
collect2: error: ld returned 1 exit status
