tarjan算法

（补充个题    牛客小白月赛12 I 题）

大佬博客

https://www.sohu.com/a/245954819_100201031

https://www.cnblogs.com/shadowland/p/5872257.html

https://blog.csdn.net/acmmmm/article/details/16361033

ac代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
vector<int>a[maxn];
int dfn[maxn],low[maxn],vis[maxn],sk[maxn],color[maxn],cnt[maxn];;
int top,deep,red;
void tarjan(int u){
    dfn[u]=++deep;
    low[u]=deep;
    vis[u]=1;
    sk[++top]=u;
    int mx=a[u].size();
    for(int i=0;i<mx;i++){
        int v=a[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else{
            if(vis[v])low[u]=min(low[u],low[v]);
        }
    }
    if(dfn[u]==low[u]){
        color[u]=++red;
        vis[u]=0;
        while(sk[top]!=u){
            color[sk[top]]=red;
            vis[sk[top]]=0;
            top--;
        }
        top--;
    }
}
int n,m,u,v;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        a[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    //统计颜色
    for(int i=1;i<=n;i++){
        cnt[color[i]]++;
    }
    //统计组合
    int ans=0;
    for(int i=1;i<=m;i++){
        if(cnt[i]>1)ans++;

    }
    printf("%d\n",ans);
    return 0;
}