#include "rings.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define F first
#define S second
#define pb push_back
#define OVL(v,s) for(auto x:v) cout<<x<<s;cout<<endl;
vector<set<int>> v;
vector<set<int>> cp;
vector<bool> visited;
vector<int> chain;
vector<int> degree;
int n;
void dfs(int node){
chain.push_back(node);
degree[node]=cp[node].size();
visited[node]=true;
for(auto x:cp[node]){
if(!visited[x]){
dfs(x);
}
}
}
bool checkchain(int node){
//so exactly two nodes got degree of 1
//and chainlength-2 nodes got degee of 2
chain.clear();
dfs(node);
int unifreq=0;
int doublefreq=0;
// dbg(node);
// OVL(chain," ")
if(chain.size()==1) return true;
for(auto x:chain){
// dbg(x,degree[x]);
if(degree[x]==1) unifreq++;
else if(degree[x]==2) doublefreq++;
else return false;
}
return (unifreq==2&&chain.size()-2==doublefreq)||chain.size()==1;
}
void Init(int N){
n=N;
visited.resize(N,false);
v.resize(N+1);
for(auto x:v) x.clear();
degree.resize(N+1,0);
}
void Link(int A, int B){
// cout<<"Link"<<A<<" "<<B<<endl;
v[A].insert(B);
v[B].insert(A);
}
int CountCritical(){
int ans=0;
for(int i=0;i<n;i++){
cp=v;
for(auto x:v[i]){
cp[i].erase(x);
cp[x].erase(i);
}
degree.assign(n,0);
visited.assign(n,false);
bool ok=true;
for(int j=0;j<n;j++){
if(!visited[j]&&j!=n){
bool x;
x=checkchain(j);
// dbg(j,x);
ok&=x;
}
}
ans+=ok;
}
return ans;
}
#ifdef IOI
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,m;
cin>>n>>m;
Init(n);
for(int i=0;i<m;i++){
int k;
cin>>k;
if(k!=-1){
int a=k;
int b;
cin>>b;
Link(a,b);
}else{
cout<<"! "<<CountCritical()<<endl;
}
}
}
#endif
Compilation message
rings.cpp:1:10: fatal error: rings.h: No such file or directory
1 | #include "rings.h"
| ^~~~~~~~~
compilation terminated.
