有向图的强连通分量

• 

• tarjan 求 scc 。

• 引入一个 时间戳 的概念。 时间戳 的定义是这个点是第几步 dfs 被搜到的。也就是 dfs 序。这样给每一个点加上一个时间戳之后可以发现，一条 树枝边 的 x 一定是小于 y 的。一条 前向边 的 x 也一定是小于 y 的。而一条 后向边 的 x 是大于 y 的，一条 横叉边 的 x 也是大于 y 的。因为横叉边只能是从右往左插。

• 对每一个点定义两个时间戳：

  1. dfn[u] 表示u的dfs序，也就是遍历到 u 的时间戳。
  2. low[u] 表示从 u 开始走，所能遍历到的最小时间戳是什么。
  3. u 是其所在的强连通分量的最高点，等价于 dfn[u] == low[u] 。

• tarjan 板子

void tarjan(int u)
{
  // 首先进行初始化，标记low、dfn，并入栈
  low[u] = dfn[u] = ++ timestamp;
  stk[ ++ top] = u, in_stk[u] = true;

  // 遍历所有的边
  for (int i = h[u]; ~i; i = ne[i])
  {
      int j = e[i];
      // 如果发现这个点没有被遍历过，dfs进去
      if (!dfn[j])
      {
          tarjan(j);
          // 回溯之后因为后面的可能有前向边让low[j]更小
          // 因此要更新一下当前点的low。
          low[u] = min(low[u], low[j]);
      }
      // 如果这条边指向的点已经在栈里了，说明这个是前向边。
      // 直接用其指向的那个点的dfs序更新自己。
      else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
  }

  // 如果相等，说明当前这个点是这个缩完之后的点中的dfs序最小的点。
  // 这里我们把栈中的全部u之前的元素（包括u）弹出，并进行scc的标记。
  if (dfn[u] == low[u])
  {
      int y = -1;
      ++ scc_cnt;
      do
      {
          y = stk[top -- ];
          in_stk[y] = false;
          id[y] = scc_cnt;
          Size[scc_cnt] ++ ; // 当前scc的大小。
      } while (y != u);
  }
}

这个板子基本上不会变。

受欢迎的牛

• 这篇文章讲得很通俗易懂 https://www.acwing.com/solution/content/20678/

• 这篇也很好 https://lishizheng.blog.csdn.net/article/details/115121867

• 这道题其实如果没有环，是一个 DAG 的话就会很好做。直接得出出度为0的点就可以。但是这道题是有环的。我们就要用到 tarjan 缩点的方法把一个环缩成一个点。 tarjan 缩点的时间复杂度是 $0(n+m)$ 。

• 缩完点之后就很简单了。首先统计缩完后每个点的出度。如果发现有两个及两个以上的点的出度为0，说明无解。否则答案是出度为0的那个点（缩完之后的点，点中不一定只有一个元素）中间元素的个数。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

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, Size[N]; // 每个强连通分量的结点个数
int dout[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
    // 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]) // 如果j没被遍历过
        {
            tarjan(j); // 继续dfs
            //j也许存在反向边到达比u还高的层，
            // 所以用j能到的最小dfn序（最高点）更新u能达到的（最小dfn序）最高点
            low[u] = min(low[u], low[j]);
        }
        // j点在栈中，说明还没出栈，是dfs序比当前点u小的
        // 要么是横叉边，要么j是u的祖宗节点
        // 两种情况u的dfs序都比j的大，所以用dfn[j]更新low[u]
        else if (in_stk[j])
        {
            low[u] = min(low[u], dfn[j]);
        }
        // 栈表示当前未被搜完的强连通分量的所有点


    }
    if (dfn[u] == low[u])
    {
        int y;
        ++ scc_cnt;
        do
        {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++ ;
        } while (y != u);
    }
}
int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    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!=-1; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];//a,b不为一个连通分量
            if (a != b) dout[a] ++ ;//a出度+1  dout[a] += i→k
        }
    int zeros = 0, sum = 0;//sum 存的所有出度为0的强连通分量的点的数量
    for (int i = 1; i <= scc_cnt; i ++ )
        if (!dout[i])//如果第i个强连通分量出度==0
        {
            zeros ++ ;
            sum += Size[i];//则加上第i个强连通分量的点的个数
            if (zeros > 1)//如果有k>1个出度为0的 则会存在k-1头牛不被所有牛欢迎
            {
                sum = 0;
                break;
            }
        }

    cout << sum;
    return 0;
}