#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
const ll N=2e5+4;
vector<ll>g[N],f[N],ob[N],bck[N],comp[N],cur,ljudi;
ll vs[N],up[N],dep[N],col[N],ar[N],sz[N],naj[N],n,m,cr,ans;
void dfst(ll u){
ljudi.push_back(u);
vs[u]=1;
for(ll v:g[u]){
if(vs[v]){
bck[u].pb(v);
bck[v].pb(u);
}else{
ob[u].pb(v);
ob[v].pb(u);
dfst(v);
}
}
}
void gd(ll u,ll p){
sz[u]=1;
for(ll v:ob[u]){
if(!(v^p))continue;
dep[v]=dep[u]+1;
gd(v,u);
sz[u]+=sz[v];
}
}
void dfsa(ll u,ll p){
up[u]=N;
cur.push_back(u);
for(ll v:ob[u]){
if(!(v^p))continue;
dfsa(v,u);
up[u]=min(up[u],up[v]);
if(up[v]>=dep[u]){
ar[u]|=1;
++cr;
comp[cr].push_back(u);
while(cur.back()!=v){
comp[cr].push_back(cur.back());
cur.pop_back();
}
comp[cr].push_back(v);
cur.pop_back();
}
}
for(ll v:bck[u])
up[u]=min(up[u],dep[v]);
}
void dfs3(ll u,ll p){
sz[u]=1;
if(u>n)--sz[u];
for(ll v:f[u]){
if(!(v^p))continue;
dfs3(v,u);
sz[u]+=sz[v];
if(u<=n)continue;
ans-=(sz[v])*(sz[v]-1)*(f[u].size()-1);
}
if(u<=n)return;
ans-=(ljudi.size()-sz[u])*(ljudi.size()-sz[u]-1)*(f[u].size()-1);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<=m;++i){
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
for(int i=1;i<=n;++i){
if(vs[i])continue;
cur.clear();
ljudi.clear();
cr=0;
dfst(i);
ans+=ljudi.size()*(ljudi.size()-1)*(ljudi.size()-2);
gd(i,i);
dfsa(i,i);
for(int j=1;j<=cr;++j){
for(ll k:comp[j]){
f[k].push_back(n+j);
f[n+j].push_back(k);
}
}
dfs3(i,i);
for(int j=1;j<=cr;++j){
for(ll k:comp[j]){
if(f[k].size())f[k].clear();
if(f[n+j].size())f[n+j].clear();
}
comp[j].clear();
}
for(ll j:ljudi)assert("jbt");
}
for(int i=1;i<=cr&&0;++i){
cout<<"comp#"<<i<<endl;
cout<<"[\n";
for(auto j:comp[i])cout<<j<<endl;
cout<<"]\n";
}
cout<<ans;
}
# | 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... |
# | 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... |