AcWing 1174. 受欢迎的牛

题目传送门

一、有向图强连通分量

在有向图\(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),   当前节点ID号
    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\)表示崇高的敬意。

网络大神的完美图解，附上以备复习之用：

三、本题题解

通过求强连通分量+缩点，可以得到一个\(DAG\)，在\(DAG\)上讨论此问题就容易了：

• 只要是出度为\(0\)的只有一个，那么此强连通分量中节点的个数就是答案。
• 如果出度为\(0\)的不只一个，那么就没有答案。
  论述过程：https://lishizheng.blog.csdn.net/article/details/115121867

四、完整代码

#include 
using namespace std;
const int N = 10010, M = 50010;
int n, m;   // n个点，m条边
int out[N]; //记录一下每个强连通分量的出度

int stk[N], top; // tarjan算法需要用到的堆栈
bool in_stk[N];  //是否在栈内
int dfn[N];     // dfs遍历到u的时间
int low[N];     // 从u开始走所能遍历到的最小时间戳
int timestamp;  // 时间戳,dfs序的标识,记录谁先谁后
int id[N], cnt; //强连通分量块的最新索引号
int sz[N];      // sz[i]表示编号为i的强连通分量中原来点的个数
/*
(1)求强连通分量

(2)缩点
for i=1;i<=n;i++
 for i的所有邻点j
   if i和j不在同一scc中:
    加一条新边id[i]→id[j]

缩点操作后变成有向无环图
就能做topsort序了(此时连通分量编号id[]递减的顺序就是topsort序了)


*/
//邻接表
int e[M], h[N], idx, ne[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// Tarjan算法求强连通分量
void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;      //初始化u节点的遍历序号(连通块号),从u开始走所能遍历到的最小时间戳
    stk[++top] = u;                     // u入栈,栈的意义一会TODO
    in_stk[u] = true;                   //标识u在栈中
    for (int i = h[u]; ~i; i = ne[i]) { //枚举u的每一条出边
        int j = e[i];
        if (!dfn[j]) {                    //如果j没有被访问过
            tarjan(j);                    // dfs继续探索
            low[u] = min(low[u], low[j]); //我孩子能到达的最小遍历序号，我也可以用
        } else if (in_stk[j])             //如果访问过，而且这个点出现在栈中，表示是后向边，回头路
            low[u] = min(low[u], low[j]); //看看是不是可以被回头路上的low[j]改的更小
    }
    if (dfn[u] == low[u]) { // 找到该连通分量的最高点
        ++cnt;              //强连通分量的序号
        int x;              //临时变量x,用于枚举栈中当前强连通分量中每个节点
        do {
            x = stk[top--];    //弹出节点
            in_stk[x] = false; //标识不在栈中了
            id[x] = cnt;       //记录id号
            sz[cnt]++;         //这个强连通分量中节点的个数+1
        } while (x != u);      //将此强连通分量中的所有节点处理完，都出栈
    }
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h); //初始化邻接表
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    //(1)求强连通分量
    for (int i = 1; i <= n; i++) //需示枚举每个点出发尝试，否则会出现有的点没有遍历到的情况
        if (!dfn[i]) tarjan(i);

    //(2)缩点，求DAG中每个节点的出度
    for (int i = 1; i <= n; i++)
        for (int j = h[i]; ~j; j = ne[j]) {
            int k = e[j];             // i->k
            int a = id[i], b = id[k]; // i,k都在哪个强连通分量块中
            if (a != b) out[a]++;     // a的出度++
        }

    /*
    当一个强连通的出度为0,则该强连通分量中的所有点都被其他强连通分量的牛欢迎
    但假如存在两个及以上个出度=0的牛(强连通分量) 则必然有一头牛(强连通分量)
    不被所有牛欢迎,见下图最右边两个强连通分量
    o→o→o
      ↑
      o→o
    */
    int zeros = 0, sum = 0;
    for (int i = 1; i <= cnt; i++) //枚举强连通分量块
        if (!out[i]) {             //如果出度是0
            zeros++;               //出度是0的强连通分量个数+1
            sum += sz[i];          //累加此强连通分量中点的个数

            if (zeros > 1) { //如果强连通分量块的数量大于1个，则无解
                sum = 0;
                break;
            }
        }
    //求有多少头牛被除自己之外的所有牛认为是受欢迎的
    printf("%d\n", sum);
    return 0;
}