#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MAXN=1e6+1;
map<ll,bool>m[MAXN];
vector<ll>grafo[MAXN];
ll n, tim, vis[MAXN], id[MAXN];
void Init(int N)
{
n=N;
}
bool dfs(ll nod, ll pad, ll prob)
{
vis[nod]=tim;
for(auto k:grafo[nod])
{
if(k==pad||k==prob||vis[k]==tim+1)
continue;
if(vis[k]==tim)
return 1;
if(dfs(k,nod,prob))
return 1;
}
vis[nod]=tim+1;
return 0;
}
int CountCritical()
{
vector<ll>cant3(n,0);
ll res=0, ban, i, j, cant=0;
ll cuat=0, pos;
for(i=0; i<n; i++)
{
if(id[i]>=4)
{
cuat++;
pos=i;
}
else if(id[i]==3)
{
for(auto k:grafo[i])
cant3[k]++;
cant3[i]++;
cant++;
}
}
if(cuat>1)
return 0;
tim=0;
memset(vis,0,sizeof(vis));
if(cuat==1)
{
tim+=2;
ban=0;
i=pos;
for(j=0; j<n; j++)
{
if(j==i)
continue;
if(vis[j]==tim+1)
continue;
if(dfs(j,0,i))
ban=1;
}
if(cant3[pos]==cant&&ban==0)
res++;
}
else
{
for(i=0; i<n; i++)
{
tim+=2;
ban=0;
for(j=0; j<n; j++)
{
if(j==i)
continue;
if(vis[j]==tim+1)
continue;
if(dfs(j,0,i))
ban=1;
}
if(ban==0&&cant3[i]==cant)
res++;
}
}
return res;
}
void Link(int a, int b)
{
if(m[a][b]==1)
return;
m[a][b]=1;
m[b][a]=1;
grafo[a].pb(b);
grafo[b].pb(a);
id[a]++;
id[b]++;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |