USACO06JAN The Cow Prom /// tarjan求强联通分量 oj24219

题目大意：

n个点 m条边的图 求大小大于1的强联通分量的个数

https://www.cnblogs.com/stxy-ferryman/p/7779347.html

tarjan求完强联通分量并染色后

计算一下每种颜色的个数 就是每个强联通块的大小

#include <stdio.h>

#include <cstring>

#include <algorithm>

#include <stack>

using namespace std;

const int N=;

struct EDGE { int to, nt; }e[*N];

int head[N], tot;

int dfn[N], low[N], ind;

int col[N], id;

bool vis[N];

stack <int> s;

int n, m, cnt[N];

void init() {

    while(!s.empty()) s.pop();

    for(int i=;i<=n;i++) {

        head[i]=dfn[i]=low[i]=col[i]=-;

        vis[i]=cnt[i]=;

    }

    tot=ind=id=;

}

void addE(int u,int v) {

    e[tot].to=v;

    e[tot].nt=head[u];

    head[u]=tot++;

}

void tarjan(int u) {

    dfn[u]=low[u]=ind++;

    s.push(u); vis[u]=;

    for(int i=head[u];i!=-;i=e[i].nt) {

        int v=e[i].to;

        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]) {

        col[u]=++id;

        vis[u]=;

        while(s.top()!=u) {

            col[s.top()]=id;

            vis[s.top()]=;

            s.pop();

        } s.pop();

    }

}

int main()

{

    while(~scanf("%d%d",&n,&m)) {

        init();

        for(int i=;i<=m;i++) {

            int u,v;

            scanf("%d%d",&u,&v);

            addE(u,v);

        }

        for(int i=;i<=n;i++)

            if(dfn[i]==-) tarjan(i);

        for(int i=;i<=n;i++)

            cnt[col[i]]++;

        int ans=;

        for(int i=;i<=id;i++)

            if(cnt[i]>) ans++;

        printf("%d\n",ans);

    }

    return ;

}