题解：B3609 [图论与代数结构 701] 强连通分量

模板题，强连通分量在本文使用 tarjan 算法进行求解。

首先是概念：

如果在有向图 $G$ 中的任意两个点都相互可达，则图 $G$ 是一个强连通图。
在有向图 $G$ 的的所有子图 $G’$中，如果 $G’$ 是一个强连通图，则图 $G’$ 为图 $G$ 的强连通子图。如果一个强连通子图 $G’$ 不是任何一个强连通子图的真子集，则图 $G’$ 为图 $G$ 的极大强连通子图，也称为 强连通分量。

然后是解决方法：

注：以下用 dfn 数组记录访问每个点的时间，用一个 low(u) 来表示 $u$ 以及其后代最多经过一条反向边能回到的最早的时间戳。

若强连通分量中第一个被发现的点是 $u$，那么集合中的点必然满足任意两点相互可达，因此最关键的就是找出每个强连通分量中的第一个点。若结点 $u$ 的子结点出发，能到达某祖先 $w$，则 $w$ 为第一个点。不难发现，若有 low[u] = dfn[u]，则有 $w = u$。

用 stack 来压入元素记录，当再次找到一个强连通分量的第一个点 $u$ 时，则弹出元素直至 $u$。因 dfs 每次只能找到若干个强连通分量，所以需要不断弹出然后用 set 记录每一个强连通分量的元素后并删除【用一个数组记录是否已经被安放至某个强连通分量中即可】，直到找到所有强连通分量。

题目中说明需要按字典序输出，因此遍历 $1-n$，用布尔数组记录该点所在强连通分量是否已经输出，这样就能完美解决了！

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <stack>
using namespace std;
const int MAX = 1e5 + 5
inline int read ();
int n,m,cnt,scc_cnt;
int to[MAX],nxt[MAX],head[MAX];
int dfn[MAX],scc[MAX],low[MAX];
bool vis[MAX];
stack <int> s;
set <int> scc_in[MAX];
void _add (int u,int v);
void dfs (int u);
int main ()
{
    n = read ();m = read ();
    for (int i = 1;i <= m;++i)
    {
        int u = read (),v = read ();
        _add (u,v);//有向图注意一下
    } 
    for (int i = 1;i <= n;++i)
        if (!dfn[i]) dfs (i);//遍历
    printf ("%d\n",scc_cnt);//个数输出
    for (int i = 1;i <= n;++i)
    {    
        int p = scc[i];//对应的强连通分量
        if (vis[p]) continue;//已经输出过
        vis[p] = 1;
        for (set <int> :: iterator it = scc_in[p].begin ();it != scc_in[p].end ();++it) printf ("%d ",*(it));//set 的输出与指针有关
        puts ("");
    }
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
void _add (int u,int v)
{
    to[++cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}
void dfs (int u)
{
    dfn[u] = low[u] = ++cnt;//时间戳
    s.push (u);//元素压入
    for (int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if (!dfn[v])
        {
            dfs (v);
            low[u] = min (low[u],low[v]);
        }
        else if (!scc[v]) low[u] = min (low[u],dfn[v]);//已经进入某个强连通分量的话就删除
    } 
    if (low[u] == dfn[u])//第一个点
    {
        ++scc_cnt;//个数加一
        while (1)//弹出
        {
            int x = s.top ();
            s.pop ();
            scc[x] = scc_cnt;
            scc_in[scc_cnt].insert (x);//记录
            if (x == u) break;
        }
    }
}