#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<ll>> adjlist;
vector<vector<ll>> bridgetree;
vector<ll> comsize;
vector<ll> majorcomponents;
vector<ll> minortomajor;
vector<ll> majsize;
ll majind = 0;
ll nc;
ll n;
ll INF = 1e9;
namespace tarjan{
vector<ll> depth;
vector<ll> hval;
stack<ll> nodesvisited;
vector<ll> components;
ll curcom = 0;
void processComponent(ll node){
ll cnt = 1;
while (nodesvisited.top()!=node){
ll t = nodesvisited.top();
components[t]=curcom;
minortomajor[curcom]=majind;
nodesvisited.pop();
cnt++;
}
components[node]=curcom;
nodesvisited.pop();
comsize.push_back(cnt);
curcom++;
}
void getHighest(ll node, ll parent){
majorcomponents[node]=majind;
ll highest = depth[node];
hval[node]=highest;
nodesvisited.push(node);
for (ll i : adjlist[node]){
if (i==parent){continue;}
if (depth[i]==INF){
depth[i]=depth[node]+1;
getHighest(i,node);
}
ll hcur = hval[i];
if (hcur<=depth[node]){
//not a bridge
highest=min(highest,hcur);
} else {
//bridge
processComponent(i);
}
}
hval[node]=highest;
}
void runBridgeDecom(){
depth.resize(n,INF);
hval.resize(n,n+1);
components.resize(n);
majorcomponents.resize(n);
minortomajor.resize(n);
for (int i = 0; i<n; i++){
if (depth[i]!=INF){continue;}
depth[i]=0;
getHighest(i,-1);
processComponent(i);
if (nodesvisited.size()>0){
comsize.push_back(nodesvisited.size());
while (nodesvisited.size()>0){
ll t = nodesvisited.top();
components[t]=curcom;
nodesvisited.pop();
}
curcom++;
}
majind++;
}
majsize.resize(majind);
for (int i = 0; i<n; i++){
majsize[majorcomponents[i]]++;
}
bridgetree.resize(curcom);
nc = curcom;
for (ll i = 0; i<n; i++){
for (ll j : adjlist[i]){
ll ix = components[i];
ll jx = components[j];
if (ix!=jx){
bridgetree[ix].push_back(jx);
bridgetree[jx].push_back(ix);
}
}
}
for (ll i = 0; i<nc; i++){
sort(bridgetree[i].begin(),bridgetree[i].end());
bridgetree[i].erase(unique(bridgetree[i].begin(),bridgetree[i].end()),bridgetree[i].end());
}
}
}
vector<ll> subtreesize;
vector<ll> tdepth;
ll dfs(ll node, ll parent){
//cout<<node<<' '<<parent<<'\n';
ll tot = 0;
subtreesize[node]=comsize[node];
ll ccnt = 0;
for (ll i : bridgetree[node]){
if (i==parent){continue;}
tdepth[i]=tdepth[node]+1;
tot+=dfs(i,node);
subtreesize[node]+=subtreesize[i];
ccnt++;
}
ll childrentot = subtreesize[node]-comsize[node];
if (ccnt>=2){
for (ll i : bridgetree[node]){
if (i==parent){continue;}
tot+=comsize[node]*subtreesize[i]*(childrentot-subtreesize[i]);
}
}
//cout<<"semit "<<tot<<'\n';
//cout<<node<<" "<<tdepth[node]<<'\n';
//consider starting at node and going up
tot+=2*tdepth[node]*childrentot;
//cout<<node<<": total "<<tot<<'\n';
return tot;
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
ll m;
cin>>n>>m;
adjlist.resize(n);
for (ll i = 0; i<m; i++){
ll a,b;
cin>>a>>b;
a--;b--;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
tarjan::runBridgeDecom();
/*for (ll i = 0; i<n; i++){
cout<<"("<<i<<": "<<tarjan::components[i]<<") ";
}cout<<'\n';
for (ll i = 0; i<bridgetree.size(); i++){
cout<<i<<" ("<<comsize[i]<<"): ";
for (ll j : bridgetree[i]){
cout<<j<<", ";
}cout<<'\n';
}*/
ll ans = 0;
// within one component
for (ll i = 0; i<nc; i++){
if (comsize[i]>=3){
ans+=comsize[i]*(comsize[i]-1)*(comsize[i]-2);
}
}
/*cout<<ans<<'\n';
for (int i : comsize){
cout<<i<<'\n';
}*/
//s+m in one component, e in other (or vice versa)
for (ll i = 0; i<nc; i++){
if (comsize[i]>=2){
//assert(majsize[majorcomponents[i]]-comsize[i]>0);
ans+=2*((comsize[i]-1)*(comsize[i]-1))*(majsize[minortomajor[i]]-comsize[i]);
}
}
//cout<<ans<<'\n';
//all three in different components
subtreesize.resize(n);
tdepth.resize(n,INF);
for (int i = 0; i<n; i++){
if (tdepth[i]!=INF){continue;}
tdepth[i]=0;
ans+=dfs(i,-1);
}
cout<<ans<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
41108 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
170 ms |
21612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
21680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
