有向图强连通分量

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. 《算法竞赛进阶指南》

一.算法简介

Tarjan 算法一种由Robert Tarjan提出的求解有向图强连通分量的算法，它能做到线性时间的复杂度。

我们定义：

如果两个顶点可以相互通达，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

例如：在上图中，{1 , 2 , 3 , 4 } , { 5 }　, { 6 } 三个区域可以相互连通，称为这个图的强连通分量。

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

再Tarjan算法中，有如下定义。

DFN[ i ] : 在DFS中该节点被搜索的次序(时间戳)

LOW[ i ] : 为i或i的子树能够追溯到的最早的栈中节点的次序号

当DFN[ i ]==LOW[ i ]时，为i或i的子树可以构成一个强连通分量。

二.算法图示

以1为Tarjan 算法的起始点，如图

顺次DFS搜到节点6

回溯时发现LOW[ 5 ]==DFN[ 5 ] , LOW[ 6 ]==DFN[ 6 ] ,则{ 5 } , { 6 } 为两个强连通分量。回溯至3节点，拓展节点4.

拓展节点1 ， 发现1再栈中更新LOW[ 4 ]，LOW[ 3 ] 的值为1

回溯节点1，拓展节点2

自此，Tarjan Algorithm 结束，{1 , 2 , 3 , 4 } , { 5 }　, { 6 } 为图中的三个强连通分量。

不难发现，Tarjan Algorithm 的时间复杂度为O(E+V).

三.算法模板

先来一段伪代码压压惊：
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) // 如果节点u还在栈内

　　　　　　　　Low[u] = min(Low[u], DFN[v])

　　if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根

　　repeat v = S.pop // 将v退栈，为该强连通分量中一个顶点

　　print v

　　until (u== v)

}

复制代码

 void Tarjan ( int x ) {
           dfn[ x ] = ++dfs_num ;
           low[ x ] = dfs_num ;
           vis [ x ] = true ;//是否在栈中
           stack [ ++top ] = x ;
           for ( int i=head[ x ] ; i!=0 ; i=e[i].next ){
                    int temp = e[ i ].to ;
                    if ( !dfn[ temp ] ){
                             Tarjan ( temp ) ;
                            low[ x ] = gmin ( low[ x ] , low[ temp ] ) ;
                  }
                  else if ( vis[ temp ])low[ x ] = gmin ( low[ x ] , dfn[ temp ] ) ;
          }
          if ( dfn[ x ]==low[ x ] ) {//构成强连通分量
                   vis[ x ] = false ;
                   color[ x ] = ++col_num ;//染色
                   while ( stack[ top ] != x ) {//清空
                            color [stack[ top ]] = col_num ;
                            vis [ stack[ top-- ] ] = false ;
                  }
                  top -- ;
          }
 }

  #include<cstdio>
  #include<algorithm>
  #include<string.h>
  using namespace std;
  struct node {
      int v,next;
  }edge[1001];
  int DFN[1001],LOW[1001];
  int stack[1001],heads[1001],visit[1001],cnt,tot,index;
 void add(int x,int y)
 {
     edge[++cnt].next=heads[x];
     edge[cnt].v = y;
     heads[x]=cnt;
     return ;    
 }
 void tarjan(int x)//代表第几个点在处理。递归的是点。
 {
     DFN[x]=LOW[x]=++tot;// 新进点的初始化。
     stack[++index]=x;//进站
     visit[x]=1;//表示在栈里
     for(int i=heads[x];i!=-1;i=edge[i].next)
     {
         if(!DFN[edge[i].v]) {//如果没访问过
             tarjan(edge[i].v);//往下进行延伸，开始递归
             LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情。
         }
         else if(visit[edge[i].v ]){  //如果访问过，并且还在栈里。
             LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子／父亲。就是链接对应关系
         }
     }
     if(LOW[x]==DFN[x]) //发现是整个强连通分量子树里的最小根。
     {
         do{
             printf("%d ",stack[index]);
             visit[stack[index]]=0;
             index--;
         }while(x!=stack[index+1]);//出栈，并且输出。
         printf("\n");
     }
     return ;
 }
 int main()
 {
     memset(heads,-1,sizeof(heads));
     int n,m;
     scanf("%d%d",&n,&m);
     int x,y;
     for(int i=1;i<=m;i++)
     {
         scanf("%d%d",&x,&y);
         add(x,y);
     }
     for(int i=1;i<=n;i++)
          if(!DFN[i])  tarjan(1);//当这个点没有访问过，就从此点开始。防止图没走完
     return 0;
 }

1.定义

在一个有向图中，如果有两个点 $(u,v)$可以在图中互相到达，那么就称这两个点是强联通的.。而如果一个有向图上的任意两点都可以互相到达，那么就成这个图为强连通图。而一个有向图中的极大强连通子图就被称为强连通分量。(极大强连通子图就是指一个强连通子图，再加入任何额外的节点都无法保证这个新的图是一个强连通图)

举个例子：

显然这个图里两个点集$[1,3,5]$和 $[2,4]$，在各自点集里的各个点都可以互相到达，且不存在更大的点集，所以称这两个点集都是强连通分量。而$[1,2]$ 和[2, 3, 4] 都不可以任意点都互相到达，所以它们不是强连通分量。

2.用处

刚刚介绍了强连通分量的定义，现在来看看强连通分量有什么用吧。
一般强连通分量都是用来缩点的，什么是缩点？就是将一些可以互相到达的点缩成一个点，能够互相到达的点当然就是强连通分量啦。那么缩点的用处是什么呢？显然你会发现在一个有向图中，所有的强连通分量就是一个个的环。你把所有的强连通分量都缩成点之后，再建出来的图，就会建出一个拓扑图(ps. 拓扑图就是有向无环图) 出来。也就是说借助强连通分量你可以将任何有向图都建成一个拓扑图，这样就可以利用很多拓扑图的性质来解题了。比如求有向图的最长/短距离或者要递推某些变量的。
而且求强连通分量的板子基本是不变

3.Tarjan算法求强连通分量

目前Tarjan算法算是比较好理解且好写的求强连通分量的方法，复杂度和维护的性质都比较优秀，Tarjan算法的时间复杂度是线性的$O(n+m)$。

(1)Tarjan的基本流程及简单证明

首先Tarjan解法是基于深度优先搜索进行遍历的算法，我们可以先假设一个dfs遍历节点的过程是类似一颗不会搜索重复节点的搜索树，那么强连通分量就是这棵树上的某几个子树。我们对这颗搜索树的边做几个定义。

1. 树枝边：即为按dfs顺序遍历到的所有的边即为树枝边
2. 前向边：这条边的一个点是另外一个点的祖先，且这条边是由深度低的点指向深度高的点(树枝边就是特殊的前向边)
3. 后向边：和前向边类似。但是是由深度高的点只想深度低的点。
4. 横插边：这条边上的两点是两颗子树上的点。且指向一定是由dfs后搜到的点指向先搜到的点

这些定义说实在的和我们讲的Tarjan并没有太大的关系…
Tarjan算法主要是引入了一个新的定义，即时间戳，时间戳说实在的就是dfs遍历的顺序，即dfs序。
Tarjan需要维护两个数组$dfn[i]$ 和 $low[i]$ 以及一个栈。$dfn[i]$ 即为搜索到的第i个节点的时间戳，而 $low[i]$ 得先介绍完栈的用处之后再解释。栈是用来在dfs回溯中，判断某个节点是否在某个还未处理完的强连通分量的。也就是说栈中存储的是按dfs序的顺序存储的还没有处理完的强连通分量的点。一旦判断出某些点是强连通分量后，就会把这些点弹出。$low[i]$ 这个数组存储的是第$i$个点包括$i$点已及还在栈中的$i$的子树能到达的时间戳最小的点的时间戳。

当$i$点以及他的子树全部遍历完了之后，如果$low[i]$ 和 $dfn[i]$ 相等，那么也就是说，$i$这个点是包括这个点的强连通分量时间戳最低的点。那么他自然不可能再加入新的节点来使他的强连通分量变得更大，即包括第$i$个结点的强连通分量已经搜完，就可以将这个结点从栈中退出来。

值得一提的是，现在栈顶到$i$个结点之间的所有结点就是这个强连通分量里的结点，所以把栈顶到$i$个结点之间的所有结点都退出来，他们构成一个强连通分量

证明： 因为首先$i$结点是这个强连通分量里时间戳最小的一个，且这个过程是在回溯时进行的，故栈中堆顶的元素到$i$点之间的结点必然是$i$结点子树上的结点，并且在$i$点之前的点肯定也不会是$i$点连通分量里的点(想想 $low$ 的定义就明白了)。又根据$low[i]$的定义，可知这些结点的$low$不可能小于$i$点的$low$，所以$i$点子树中不属于$i$点的连通分量的结点，它们所在的联通分量上的结点也只可能在$i$点的子树内，而$i$点的子树已经全部处理完了，所以，在回溯到$i$点之前，那些不属于$i$点联通分量的结点必然在之前已经处理完，并退出栈内。所以剩下的点必然都是属于$i$点联通分量上的结点。（Tarjan牛逼啊）

(2)代码模板

Tarjan算法的模板比较固定，基本上不会做太多的改变，所以一般做题的话，可以直接套板子处理有向图。

补充：一个点就是我看到很多人写完Tarjan后，还会再进行一次拓扑排序，其实完全没有必要，可以注意到，拓扑排序中有一种dfs的写法和Tarjan算法的做法很类似，所以Tarjan后缩点的图的拓扑序，就是这个缩点图的点编号的倒序输出。

vector<int> G[N], D[N]; 
int f[N], g[N];
int dfn[N], low[N], tim, idx, scc_idx; //tim为时间戳,idx为栈顶下标，scc_idx为强连通分量个数
int sta[N], sz[N], id[N];			//sta为栈，sz为缩点后的点里包括多少个点，id为缩点见图后的新下标
bool in_sta[N];						//in_sta为检查某个结点是否还在栈内

void tarjan(int u){
	dfn[u] = low[u] = ++ tim;
	sta[++idx] = u; in_sta[u] = true;
	for(int i = 0;i < G[u].size();i++){
		int v = G[u][i];
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if(in_sta[v]) low[u] = min(low[u],low[v]);
	}
	if(low[u] == dfn[u]){
		scc_idx++;
		int y;
		do{
			y = sta[idx--];
			in_sta[y] = false;
			id[y] = scc_idx;
			sz[scc_idx]++;
		}while(y != u);
	}
}

(3)例题

a. USACO 2003 Fall (受欢迎的牛)

题目描述

每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。

输入

第一行两个数 N,M；

接下来 M 行，每行两个数 A,B，意思是 A 认为 B 是受欢迎的（给出的信息有可能重复，即有可能出现多个 A,B）。

输出

输出被除自己之外的所有牛认为是受欢迎的牛的数量。

输入样例

3 3
1 2
2 1
2 3

输出样例

1

数据范围：

对于全部数据，$1\le N\le 10^4,1\le M\le 5\times 10^4$

题解

对于这道题没啥好说的，缩完点直接出度为0的点有多少，超过1个的答案就是0。否则就是那个点的大小(大小就是缩点前的这个强连通分量包括几个点)

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+50;

vector<int> G[N];
int tim, sta[N], sz[N], id[N], idx; 
int scc_idx, dfn[N], low[N], du[N];
bool in_sta[N];

void tarjan(int u){
	dfn[u] = low[u] = ++tim;
	sta[++idx] = u; in_sta[u] = true;
	for(int i = 0;i < G[u].size();i++){
		int v = G[u][i];
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(in_sta[v]){
			low[u] = min(low[u], low[v]);
		}
	}
	if(low[u] == dfn[u]){
		int y;
		scc_idx++;
		do{
			y = sta[idx--];
			in_sta[y] = false;
			id[y] = scc_idx;
			sz[scc_idx]++;
		}while(u != y);
	}
}

int main(){
	int n, m;
	scanf("%d %d",&n,&m);
	while(m--){
		int a, b;
		scanf("%d %d",&a,&b);
		G[a].push_back(b);
	}
	for(int i = 1;i <= n;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < G[i].size();j++){
			if(id[G[i][j]] != id[i]) du[id[i]]++;
		}
	}
	int ans = 0, tmp = 0;
	for(int i = 1;i <= scc_idx;i++){
		if(du[i] == 0) ans = sz[i], tmp++;
	}
	if(tmp > 1) printf("0\n");
	else printf("%d\n",ans);
	return 0;
}

b.《算法竞赛进阶指南》, usaco training 5.3 （学校网络）

题目描述

一些学校连接在一个计算机网络上，学校之间存在软件支援协议，每个学校都有它应支援的学校名单（学校 A 支援学校 B，并不表示学校 B 一定要支援学校 A）。

当某校获得一个新软件时，无论是直接获得还是通过网络获得，该校都应立即将这个软件通过网络传送给它应支援的学校。

因此，一个新软件若想让所有学校都能使用，只需将其提供给一些学校即可。

现在请问最少需要将一个新软件直接提供给多少个学校，才能使软件能够通过网络被传送到所有学校？

最少需要添加几条新的支援关系，使得将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件？

输入格式

第 1 行包含整数 N，表示学校数量。

第 2…N+1 行，每行包含一个或多个整数，第 i+1 行表示学校 i 应该支援的学校名单，每行最后都有一个 0 表示名单结束（只有一个 0 即表示该学校没有需要支援的学校）。

输出格式

输出两个问题的结果，每个结果占一行。

数据范围

2≤N≤100

输入样例：

5
2 4 3 0
4 5 0
0
0
1 0

输出样例：

1
2

题解

这个题目第一问很简单，就是缩点后入读为0的点的个数。
第二问的答案则是入读为0的点和出度为0的点取最大值。
这边只证明第二问：假设有$p$和入读为0的点，$q$个初读为0的点，这边先假设$(p<=q)$，$(p>q)$ 的证明类似。
我们称出度为0的点为终点，入读为0的点为起点
首先可以肯定地是一个终点总有一个起点可以到达它。
我们先看$p=1$的时候

如果$p=1$ 那么也就是说这个起点可以到达所有的终点，即只要让每个终点都和起点连一个边即可即$q$条边。

如果$p>1$ 那么必然可以找到两组不同的起点$(q1,q2)$走到不同的终点$(p1,p2)$。 即$(q1->p1)$$(q2->p2)$。于是我们总可以建一个 $(p1->q2)$ 的边使得起点和终点各减少一个。最后会变为 $q=1$ 的情况。所以发现我们总可以只建$max(p,q)$个边使得起成为整个图变成强连通分量。并且一定是最优的。

然后在特判一下，如果整个图只有一个强连通分量，那么第二问答案就是0。

代码

//强联通分量可以把任意有向图转化为一个有向无环图(拓扑图)，并且使用tarjan 算法求出的强连通分量的编号逆向输出就是这个拓扑图的拓扑序 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+50;

vector<int> G[N];
bool in_sta[N];
int id[N], low[N], dfn[N], sta[N];
int tim, in[N], out[N], scc_idx, idx; 

void tarjan(int u){
	dfn[u] = low[u] = ++tim;
	sta[++idx] = u; in_sta[u] = true;
	for(int i = 0;i < G[u].size();i++){
		int v = G[u][i];
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u], low[v]); 
		}
		else if(in_sta[v]) low[u] = min(low[u],dfn[v]);
	}
	if(low[u] == dfn[u]){
		int y;
		scc_idx++;
		do{
			y = sta[idx--];
			in_sta[y] = false;
			id[y] = scc_idx;
		}while(y != u);
	}
}

int main(){
	int n;
	scanf("%d",&n);
	int ans1 = 0, ans2 = 0;
	for(int i = 1;i <= n;i++){
		int x;
		while(scanf("%d",&x) && x != 0) G[i].push_back(x);
	}
	for(int i = 1;i <= n;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < G[i].size();j++){
			int v = id[G[i][j]];
			if(v != id[i]) {
				in[v]++; out[id[i]]++;
			}
		}
	}
	for(int i = 1;i <= scc_idx;i++){
		if(in[i] == 0) ans1++;
 		if(out[i] == 0) ans2++;
	}
	printf("%d\n",ans1);
	if(scc_idx == 1) printf("0\n");
	else printf("%d\n",max(ans1,ans2));
	return 0;
}
/*
5
2 4 3 0
4 5 0
0
0
1 0
*/