鄙人不才，此中鄙陋甚多，望海涵！！！

题意分析,n个点，m条单向边，(10000点，100000边)问有多少点对间可以互通，我们都知道，在有向图中环中的任意2点互通，在一个有n个点的环中，互通的点对有res=n*(n-1)/2对，因此我们只要知道在我们的图中有多少环以及环中有多少点即可，而我们又知道SCC（有向图的强连通分量）便是一个将我们的图变为拓扑图的算法，在tarjan算法中，我们可以将一个内部可以相互到达的最大环缩点，即变成一个大点，我们也会记录这个大点(其实就是之前的那个环)中有多少点，这也我们就可以在SCC后的拓扑图中计算点对了！（tarjan为O(n+m)复杂度，秒过）

稍加分析会发现其实是SCC裸题，难度不大，详见代码！

C++Code

#include<iostream>
#include<cstring>

using namespace std;

const int N=1e4+10,M=1e5+10;

int h[N],e[M],ne[M],w[M],idx;
int scc_cnt,timestamp,stk[N],top;
int low[N],dfn[N],se[N];
bool in_stk[N];
int n,m;

void add(int a,int 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(low[u]==dfn[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            se[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    int ans=0;
    for(int i=1;i<=scc_cnt;i++)   ans+=se[i]*(se[i]-1)/2;
    cout<< ans <<endl;
    return 0;
}

创作不易，如果您觉得对您有帮助，就点个赞支持一下！您的赞就是我持续更新优质题解的动力！