1 条题解

  • 0
    @ 2026-6-20 16:42:01
    // Tarjan算法 O(n+m)
    #include<bits/stdc++.h>
    using namespace std;
    
    const int N=10010;
    int n,m,ans;
    vector<int> e[N]; 
    int dfn[N],low[N],tim,stk[N],top,scc[N],siz[N],cnt;
    
    void tarjan(int u){
      dfn[u]=low[u]=++tim; stk[++top]=u;
      for(int v:e[u]){
        if(!dfn[v]){ //若v尚未访问
          tarjan(v);
          low[u]=min(low[u],low[v]);
        }
        else if(!scc[v]) //若v已访问且未构成SCC
          low[u]=min(low[u],dfn[v]);
      }
    
      if(low[u]==dfn[u]){ //若u不是SCC的根,则low<dfn
        ++cnt;
        for(int v=-1;v!=u;){
          v=stk[top--];
          scc[v]=cnt; //SCC的编号
          ++siz[cnt]; //SCC的大小
        }
      }
    }
    int main(){
      ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
      cin>>n>>m;
      for(int a,b;m--;) cin>>a>>b,e[a].push_back(b);
      for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);
      for(int i=1;i<=cnt;i++)if(siz[i]>1) ans++;
      cout<<ans;
    }
    
    • 1

    信息

    ID
    2616
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    6
    已通过
    6
    上传者