和提高课例题没差
$\quad$1.tarjan求连通块并统计每个连通块内点的数量
$\quad$2.对每个连通块内点的数量做一次$C^2_n$
#include <bits/stdc++.h>
using namespace std;
const int N=10010,M=100010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp; // 时间戳
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt,sz[N]; // 每个点所属分量编号
int n,m;
typedef long long ll;
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j])
low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u])
{
++ scc_cnt;
int y;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
sz[scc_cnt]++;
} while (y != u);
}
}
ll get(int x){
return 1ll*x*(x-1)/2;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- ){
int a,b;
scanf("%d%d",&a,&b);
add(a, b);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
ll ans=0;
for(int i=1;i<=scc_cnt;i++){
ans+=get(sz[i]);
}
cout<<ans;
return 0;
}