AcWing 3220. 高速公路
原题链接
中等
作者:
云_580
,
2025-03-26 19:30:20
·山东
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
const int N = 1e4+10;
int n,m,top,idx,cnt;
int dfn[N],low[N],stk[N],instk[N],scc[N],siz[N];
vector<int>e[N];
void tarjan(int u){
dfn[u]=low[u]=++idx;
stk[++top]=u;instk[u]=1;
for(int v:e[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(instk[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
int y;++cnt;
do{
y=stk[top--];
instk[y]=0;
scc[y]=cnt;
++siz[cnt];
}while(y!=u);
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>m;
for(int i = 1;i<=m;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
}
for(int i = 1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
int ans = 0;
for(int i = 1;i<=cnt;i++){
if(siz[i]>=2){
ans+=siz[i]*(siz[i]-1)/2;
}
}
cout<<ans;
return 0;
}