摘要

强连通分量常用于缩点，是图论中一个重要的知识点。本文首先介绍了强连通分量的相关定义以及其应用范围，然后将着重介绍两种求强连通分量的算法：Kosaraju算法以及Tarjan算法，它们的时间复杂度都是O(n+m)（n：顶点数，m：边数）。
其中Kosaraju算法思想简单，操作方便，易于理解与代码实现，但是性能以及拓展性上比Tarjan略逊一筹；本文将会逐一介绍这两种算法的思想以及实现步骤，最后会以例题的形式给出代码模板。

相关定义

在有向图G中，如果两个顶点u，v间存在一条 u 到 v 的路径且也存在一条 v 到 u 的路径，则称这两个顶点u，v 是强连通的（strongly connected）。如果有向图G的任意两个顶点都强连通，则称G是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量（strongly connected components）。

极大强连通子图： G是一个极大强连通子图，当且仅当G是一个强连通子图且不存在另一个强连通子图G’，使得 G 是 G’ 的真子集。

强连通分量的应用

若将有向图中的强连通分量都缩为一个点，则原图会形成一个DAG（有向无环图），如图1所示:

图1：虚线部分构成一个强连通分量（图片来自ccf的博客）

强连通分量的常见用途有两个：

• 有向图的缩点。
• 解决2-SAT问题。

Kosaraju 算法

Kosaraju算法的时间复杂度是O(n+m)，基于两次DFS的有向图强连通子图算法。
该算法共分为三步：

第一步，对原有向图G进行DFS，记录节点访问完的顺序d[i] , d[i] 表示第 i 个访问完的节点是d[i]；
第二步，选择具有最晚访问完的顶点，对反向图GT 进行DFS，删除能够遍历到的顶点，这些顶点构成的一个强连通分量。
第三步，如果还有顶点没有删除，继续第二部，否则算法结束。

代码实现：

见附录部分 code-1：Kosaraju算法模板（POJ2186）

Tarjan算法

Tarjan算法是 Robert Tarjan 发明的一个算法，其时间复杂度也是O(n+m)，但我们之所以在掌握了Kosaraju算法后仍要学习Tarjan算法的主要原因有以下三点：

• Tarjan算法效率比Kosaraju算法高大概30%，所以Kosaraju可能会被卡常。
• Kosaraju算法利用递归实现，可能会爆栈；而Tarjan则不会（因为根本没递归）。
• Tarjan算法还可以通过拓展解决求割点、割桥以及2-SAT等问题。

实际上如果出题人有这个想法，那么就不是可能会超时，是一定会超时；不是可能会爆栈，是一定会爆栈，所以还是要掌握该算法的。

基本概念

Tarjan算法是基于对图深度优先搜索（DFS）的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个栈，回溯时可以判断栈顶到栈中的节点是否构成一个强连通分量。
我们定义DFS过程中遇到的四种边：

• 树枝边：DFS时经过的边，即DFS搜索树上的边。
• 前向边：与DFS方向一致，从某个节点指向其某个子孙的边。
• 后向边：与DFS方向相反，从某个节点指向其某个祖先的边。
• 横向边：从某个节点指向搜索树中另一子树中的某节点的边。

定义DFN(u) 为节点 u 的搜索次序编号（时间戳），Low(u) 为u 或者u 的子树能够回溯到的最早的栈中节点的DFN值。

根据定义我们可以得出：

• 如果(u , v)为树枝边，u 为 v 的父节点，则 Low(u) = min{ Low(u) , Low(v) }。
• 如果(u , v)为后向边或指向栈中节点的横叉边，则Low(u) = min{ Low(u) , DFN(v) }。

当节点u的搜索过程结束后，若DFN(u) = Low(u)，则以u为根的搜索子树上所有还在栈中的节点（即u和栈中在u之后的所有节点）是一个强连通分量，可退栈。通俗的说，若u为强连通分量的根，那么它的子孙中的最高最先应该就是它本身。

算法的主要过程

数组的初始化： 当首次搜索到点 u 时，DFN(u)为节点u的搜索次序编号（时间戳）。
堆栈： 将u压入堆栈。
更新Low(u)：

1. 如果（u，v）为树枝边（v不在栈中），u为v的父节点，则Low(u) = min{Low(u) , Low(v)}。
2. 如果（u，v）为后向边或者指向栈中节点的横叉边（v在栈中），则Low(u) = min{ Low(u) DFN(v)}。
3. 如果u的子树已经全部遍历后Low(u) = DFS(u)，则将u和栈中在u之后的所有节点 弹出栈。这些出栈的元素组成一个强连通分量。
4. 继续搜索（或许会更换搜索的起点，因为整个有向图可能分为多个不连通的部分），直到所有点被遍历。

代码实现

见附录部分code-2：POJ2182（Tarjan算法）

参考资料

• 董永建，信息学竞赛一本通提高篇，福州：福建教育出版社，2018.6，155-178
• 秋叶拓哉，挑战程序设计竞赛第2版，北京：人民邮电出版社，2013.6，320-324

附录

code-1：Kosaraju算法模板（POJ2182）
求所有“红牛”总数。（红牛即所有牛的偶像）

/*******************************************************************
    最后修改：2019/8/15 Valenshi
    使用说明：
        用数组表示邻接表,分别建立了正图和反图;
        只适用于节点从1~n的题型,切记若干节点编号是0~n-1会死循环!
        主函数：scc(),用于求所有强连通分量,O(N+M),答案存放在kos数组。
 *******************************************************************/
#include<cstdio>
#include<cstring>
const int N = 1e4+10;
const int M = 5e4+10;

int head[N],ver[M],nex[M],tot;  //邻接表存放有向图
int rhead[N],rver[M],rnex[M],rtot;//存放反图
int vis[N],kos[N];//访问标记;节点所属联通分量标号
int ts[N],tc;  //时间戳, dfs访问时的顺序;tc为当前"时间"
void addEdge(int x,int y){
    /* 建立一条从x->y的有向边 , 同时在反图添加一条从y->x的有向边*/
    ver[++tot] = y,nex[tot] = head[x], head[x] = tot;
    rver[++rtot] = x,rnex[rtot] = rhead[y],rhead[y] = rtot;
}

void dfs(int x){
    /*给节点x以及它的子孙打上时间戳*/
    vis[x] = true;
    for(int i = head[x] ;i ;i = nex[i]){
        int y = ver[i];
        if(!vis[y]) dfs(y);
    }
    ts[++tc] = x;     //第tc个回溯的是点x
}

void rdfs(int x,int k){
    /* 找出属于第k个强连通分量的所有点 */
    vis[x] = true;kos[x] = k;
    for(int i = rhead[x];i ;i = rnex[i]){
        int y = rver[i];
        if(!vis[y]) rdfs(y,k);
    }
}
int n,m;      //点的个数,编号为1~n;
int scc(){
    /* 将原图分为若干强连通分量,并返回个数 */
    memset(vis,0,sizeof vis);tc = 0;
    for(int i = 1;i <= n;i++)
        if(!vis[i]) dfs(i);
    memset(vis,0,sizeof vis);
    int k = 0;
    for(int i = tc;i > 0;i--) if(!vis[ts[i]]) rdfs(ts[i],++k);
    return k;
}
/***********************************
	以下为POJ2186解题代码 
 ***********************************/
int A[N],B[N];
void solve(){
	int k = scc();		//备选答案总数 
	int y = 0,sum = 0;
	for(int i = 1;i <= n;i++){
		if(kos[i] == k){
			y = i;sum++;
		}
	}
	//检查是否从所有点可达
	memset(vis,0,sizeof vis);
	rdfs(y,0);	//代码重用
	for(int i = 1;i <= n;i++){
		if(!vis[i]){
			sum = 0;break;
		}
	} 
	printf("%d\n",sum);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1,x,y;i <= m;i++){
		scanf("%d%d",&x,&y);
		addEdge(x,y);
	}
	solve();
    return 0;
}

code-2：POJ2182（Tarjan算法模板）

/***************************************************************
	最后更新：2019/8/16 ValenShi
	使用说明：
		1.记得初始化辅助数组dfn[],co[],head[],
		以及"数组指针" ,top,tot,num,col ;
		2.每个辅助数组具体作用见注释;
		3.节点范围是1~n,若是0~n-1会死循环,可更改head[]初始值解决。 
***************************************************************/ 
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 1e4+10;
const int M = 1e5+10;
/* 邻接表存有向图 */
int head[N],ver[M],nex[M],tot;
inline void addEdge(int x,int y){
	ver[++tot] = y,nex[tot] = head[x],head[x] = tot;
}
/***************************************** 
Tarjan算法及其辅助数组：
	Stack[]为栈,top为栈顶指针;
	dfn[]为节点的时间戳,num为对应的"时间";
	co[]为节点所在的强连通分量的编号,col对应编号; 
******************************************/ 
int n,m;
int Stack[N],top;
int dfn[N],low[N],num,co[N],col;
void Tarjan(int u){
	dfn[u] = low[u] = ++num;
	Stack[++top] = u;
	for(int i = head[u];i ;i = nex[i]){
		int v = ver[i];
		if(!dfn[v]){
			Tarjan(v);
			low[u] = min(low[u],low[v]);
		}else if(!co[v]) low[u] = min(low[u],dfn[v]);
	}
	if(low[u] == dfn[u]){
		co[u] = ++col;
		while(Stack[top] != u){
			co[Stack[top]] = col;
			top--;
		}
		top--;
	}
}
int chudu[N];/*用来记录每个强连通分量的出度 */ 
void solve(){
	num = col = top = 0;
//	memset(dfn,0,sizeof dfn);
//	memset(co,0,sizeof co);
//	memset(chudu,0,sizeof chudu); 
	for(int i = 1;i <= n;i++) if(!dfn[i]) Tarjan(i);
	int ans = 0,tcnt = 0;
	/*ans存放答案,tcnt表示出度为0的强连通分量的个数*/ 
	for(int i = 1;i <= n;i++){
		for(int j = head[i];j ;j = nex[j]){
			int y = ver[j];
			if(co[i] != co[y]) chudu[co[i]]++;
			/*i所在的强连通分量的出度+1 */
		}
	}
	int tcol = 1;/*tcol为出度为0的强连通分量的编号*/
	for(int i = 1;i <= col;i++) if(!chudu[i]) tcnt++,tcol = i;
	for(int i = 1;i <= n;i++) if(co[i] == tcol) ans++;
	if(tcnt > 1) puts("0");
	else printf("%d\n",ans);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1,u,v;i <= m;i++){
		scanf("%d%d",&u,&v);
		addEdge(u,v);
	}
	solve();
	return 0;
}

有向图的强连通分量

在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。

直接根据定义，用双向遍历取交集的方法求强连通分量，时间复杂度为O(N^2+M)。更好的方法是Kosaraju算法或Tarjan算法，两者的时间复杂度都是O(N+M)。本文介绍的是在实践中略胜一筹的Tarjan算法。

Tarjan算法

Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出：

Low(u)=Min
{
    DFN(u),
    Low(v),(u,v)为树枝边，u为v的父节点
    DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)
}

当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。

算法伪代码如下：

tarjan(u)
{
	DFN[u]=Low[u]=++Index                      // 为节点u设定次序编号和Low初值
	Stack.push(u)                              // 将节点u压入栈中
	for each (u, v) in E                       // 枚举每一条边
		if (v is not visted)               // 如果节点v未被访问过
			tarjan(v)                  // 继续向下找
			Low[u] = min(Low[u], Low[v])
		else if (v in S)                   // 如果节点v还在栈内
			Low[u] = min(Low[u], DFN[v])
	if (DFN[u] == Low[u])                      // 如果节点u是强连通分量的根
		repeat
			v = S.pop                  // 将v退栈，为该强连通分量中一个顶点
			print v
		until (u== v)
}

接下来是对算法流程的演示。

从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=v为止，{6}为一个强连通分量。

返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。

返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW[4]=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。

继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=DFN[4]=5。返回1后，发现DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。

至此，算法结束。经过该算法，求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。

可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。

求有向图的强连通分量还有一个强有力的算法，为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。与Trajan算法相比，Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS，不用建立逆图，更简洁。在实际的测试中，Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外，该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法，也有助于深入理解求双连通分量的Tarjan算法，两者可以类比、组合理解。

求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法，以及求最近公共祖先的离线Tarjan算法，在此对Tarjan表示崇高的敬意。

tarjan算法的C++实现

void tarjan(int i)
{
	int j;
	DFN[i]=LOW[i]=++Dindex;
	instack[i]=true;
	Stap[++Stop]=i;
	for (edge *e=V[i];e;e=e->next)
	{
		j=e->t;
		if (!DFN[j])
		{
			tarjan(j);
			if (LOW[j]<LOW[i])
				LOW[i]=LOW[j];
		}
		else if (instack[j] && DFN[j]<LOW[i])
			LOW[i]=DFN[j];
	}
	if (DFN[i]==LOW[i])
	{
		Bcnt++;
		do
		{
			j=Stap[Stop--];
			instack[j]=false;
			Belong[j]=Bcnt;
		}
		while (j!=i);
	}
}
void solve()
{
	int i;
	Stop=Bcnt=Dindex=0;
	memset(DFN,0,sizeof(DFN));
	for (i=1;i<=N;i++)
		if (!DFN[i])
			tarjan(i);
}

有向图强连通分量

1.定义：

给定一张有向图，若对于图中任意两个节点x，y，既存在从x到y的路径，也存在y到x的路径，则该有向图是强连通图。
有向图的极大强连通子图被称为：强连通分量，简称SCC(Strongly connected component)
Tarjan 算法基于dfs，可以在线性时间内求出一张有向图的所有连通分量。

2.基本术语与概念

2.1 边的概念

1.树枝边：搜索树中给定两个点x,y，x是y的父亲节点，那么这条边就是树枝边

2.前向边：搜索树中给定两个点x,y，x是y的祖先节点，那么这条边就是前向边

3.后向边：搜索树中给定两个点x,y，y是x的祖先节点，那么这条边就是后向边

4.横叉边：搜索树中给定两个点x,y，不属于以上三种的边，就叫横叉边，且y在搜索树中的编号一定小于x在搜索树中的编号。即dfn[y]<dfn[x]，（连向其他搜索过的节点的边），可以发现：往左边的横叉边是横叉边，往右边的横叉边实际上是树枝边，因为右边的节点还没有被搜过。

举个例子：

dfn数组存储的即是各个深度优先遍历过程中，每个节点第一次被访问的时间顺序，读者不妨对该图做一次深度优先遍历加以验证。
例如：1,2即是树枝边，注意：树枝边一定也是前向边
1,8即是前向边，4,6即是后向边，8,7是横叉边

2.2 缩点

将所有连通分量缩成一个点。

2.3 时间戳

在搜索的时候，按照深度优先遍历顺序给每个点一个编号，即时间戳。
dfn[u]表示遍历到u的时间戳。

3. tarjan求强连通分量（SCC）

3.1 原理

1. 把边分成四大类：树枝边，前向边，后向边，横叉边
2. 取一个点x，判断它是否在强连通分量中
   情况1：存在一条后向边使得它可以走到某个祖先节点
   情况2：存在一条横叉边，它先通过横叉边，然后横叉边所在的点可以走到某个祖先节点
   以上两种情况，点x和它的祖先节点之间所有节点都可以互相到达，满足强连通分量的定义。

3.2 步骤

1. 给每个点定义两个时间戳：
   dfn[u]表示遍历到u的时间戳，即dfs的搜索顺序
   low[u]表示从u开始走，所能遍历到的最小时间戳
2. u是其所在强连通分量的最高点，等价于dfn[u]==low[u]

3.3 模板

3.3.1 tarjan求强连通分量的过程

void tarjan(int u)
{
   dfn[u] = low[u] = ++timestamp;//时间戳
   stk[++top] = u,in_stk[u] = true;//把当前点放到栈里面去，随后标记u已经入栈
   for(int i = h[u];~i;i = ne[i])
   {
       int j = e[i];
       if(!dfn[j])
       {
           tarjan(j);//先看一下u能到的点
           //这里做完tarjan(j)以后，low[j]已经被更新了，由定义可知，low[j]保存的就是从j出发能到达的时间戳最小的点
           low[u] = min(low[u],low[j]);//更新low[u]
       }
       else if(in_stk[j])
       {
           //可能通过其他边能搜到j，但不是当前分支搜到的，读者这里可以好好考虑考虑
           //stk不一定只存了当前分支的点，还可能存有前面其他分支的点，比如横叉边所到达的点
           //stk存的是当前还没有遍历完的强连通分量的所有点
           low[u] = min(low[u],dfn[j]);
       }
   }
   if(dfn[u]==low[u])
   {
       //u必然是u所在的强连通分量的最高点（由定义）
       int y;
       ++scc_cnt;
       do{
           y = stk[top--];//把栈顶弹出
           in_stk[y] = false;//标记它没有在栈里面
           id[y] = scc_cnt;//标记y这个点属于scc_cnt这个强连通分量
       }while(y!=u);
   }
}
// y总原话：《最好背过》 :)

3.3.2 缩点的过程

for(int i = 1;i<=n;i++)
{
   for(i的所有邻点j)
   {
       if(i和j不在同一个强连通分量中)
       {
           把i所在的强连通分量向j所在的强连通分量加一条边;
       }
   }
}
//缩完点就是DAG(有向无环图)

注：缩完点以后，连通分量编号递减的顺序一定是拓扑序

给出注的证明:
对于一个图做一遍深度优先遍历，把每个点加入序列seq中
显然有seq的逆序即是拓扑序。

for(int i = h[u];~i;i = ne[i])
{
    int j = e[i];
    if(!st[j])
    {
        seq<-j;//把j存入seq序列中
        dfs(j);
    }
}
//读者不妨验证一下

最后，观察tarjan求有向图强连通分量的过程实际上就是对图做深度优先遍历的过程,所以最后按连通分量编号递减的顺序输出一定是拓扑序

4.例题

题目1：P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G

一个思路是建反图，对每个奶牛做一遍dfs，统计完美奶牛个数，时间复杂度O(nm)，显然超时。
再观察：
题意知当是有向无环图时，只要有两个点出度为0，那么完美奶牛个数为0，如果有一个出度为0，那么完美奶牛个数为1，
于是可以tarjan缩点，如果只有一个出度为0的强连通分量，那么答案就是该强连通分量的size。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10,M = 5e4+10;
int n,m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;  // 时间戳
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt;  // 每个点所属分量编号
int dout[N],sz[N];//出度数组

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(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt]++;
        }while(y!=u);
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin>>n>>m;    
    while (m -- ){
        int a,b;
        cin>>a>>b;
        add(a, b);
    }
    for(int i = 1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    for(int i = 1;i<=n;i++)
    {
        for(int j = h[i];~j;j = ne[j])
        {
            int k = e[j];
            int a = id[i],b = id[k];
            if(a!=b)
            {
                //说明i和j不在同一个连通分量中
                dout[a]++;//这里没有实际把边加出来，因为不在同一个连通分量中，所以要把a的出度+1，等价于加了一条边
            }
        }
    }
    int sum = 0,zeros = 0;//zeros记录出度为0的连通分量的个数
    for(int i = 1;i<=scc_cnt;i++)
    {
        if(!dout[i])
        {
            zeros++;
            sum+=sz[i];
            if(zeros>1)
            {
                cout<<0;
                return 0;
            }
        }
    }
    cout<<sum;
    return 0;
}

题目2：P2746 [USACO5.3]校园网Network of Schools

第一个问类似题目1，第二个问需要找小性质：如何让有向无环图变成强连通图添加的边的数量最少？
$$\begin{gathered} 设a为入度为0的点的个数，b为出度为0的点的个数 \\ 那么易有ans=max(a,b) \end{gathered}$$
题解来自《算法竞赛进阶指南》：

AC code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10,M = 5e4+10;
int n,m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;  // 时间戳
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt;  // 每个点所属分量编号
int dout[N],sz[N],din[N];//出度数组

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(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt]++;
        }while(y!=u);
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        int x;
        while(cin>>x,x)
        {
            add(i,x);
        }
    }
    for(int i = 1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    for(int i = 1;i<=n;i++)
    {
        for(int j = h[i];~j;j = ne[j])
        {
            int k = e[j];
            int a = id[i],b = id[k];
            if(a!=b)
            {
                //说明i和j不在同一个连通分量中
                dout[a]++;//这里没有实际把边加出来，因为不在同一个连通分量中，所以要把a的出度+1，等价于加了一条边
                din[b]++;
            }
        }
    }
    int sum1 = 0,sum2 = 0,cnt1 = 0,cnt2 = 0;
    //cnt1记录出度为0的连通分量的个数
    //cnt2记录入度为0的连通分量的个数
    for(int i = 1;i<=scc_cnt;i++)
    {
        if(!dout[i])
        {
            cnt1++;
        }
        if(!din[i])
        {
            cnt2++;
        }
    }
    if(scc_cnt!=1)
        cout<<cnt2<<endl<<max(cnt1,cnt2);
    else
        cout<<cnt2<<endl<<"0";
    return 0;
}

陆续更新~

5.参考资料

1. acwing算法提高课图论
2. 《算法竞赛进阶指南》