作者:
Unkillable
,
2023-05-26 12:38:57
,
所有人可见
,
阅读 10
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 50;
const int M = 1e5 + 50;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N];
int stk[N], top, ts;
bool in_stk[N];
int res;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ts;
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])
{
int y, cnt = 0;
do
{
y = stk[top --];
in_stk[y] = false;
cnt++;
}while(y != u);
res += cnt * (cnt - 1) / 2;
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m --)
{
int a, b;
cin >> a >> b;
add(a, b);
}
for(int i = 1; i <= n; i++)
{
if(!dfn[i])
tarjan(i);
}
cout << res;
return 0;
}