目录

什么是连通图？

什么是连通分量？

那什么是极大连通子图呢？联想到的极小连通子图又是什么呢？

强连通图

强连通分量

”强强“在那里—连通图和强连通图的区别？

创作不易，不妨点赞💚评论❤️收藏💙一下

想要了解更多吗？没时间解释了，快来点一点！

💟作者简介：大家好呀！我是路遥叶子，大家可以叫我叶子哦！❣️    
📝个人主页：【路遥叶子的博客】
🏆博主信息：四季轮换叶，一路招摇胜！

               专栏

        【安利Java零基础】

        【数据结构-Java语言描述】

🐋希望大家多多支持😘一起进步呀！~❤️
🌈若有帮助，还请【关注➕点赞➕收藏】，不行的话我再努力努力呀！💪
————————————————
🍁想寻找共同成长的小伙伴，请点击【Java全栈开发社区】

前言

对连通图的理解

在图论中，连通图基于连通的概念。

在一个 无向图G 中，若从顶点 i 到顶点 j 有路径相连（当然从j到i也一定有路径），则称i和j是连通的。

如果 G 是有向图，那么连接 i 和 j 的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。图连通性的是图的基本性质。

一、什么是连通图？

连通：在无向图中，若从顶点u到顶点v有路径，则称u和v是连通的。

图中从⼀个顶点到达另⼀顶点，若存在⾄少⼀条路径，则称这两个顶点是连通着的。例如图 1 中，虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径，分别是 V1-V2-V3 和 V1-V4-V3，因此称 V1 和 V3 之间是连通的。

  二、什么是连通分量？

若⽆向图不是连通图，但图中存储某个⼦图符合连通图的性质，则称该⼦图为连通分量。
由图中部分顶点和边构成的图为该图的⼀个⼦图，但这⾥的⼦图指的是图中"最⼤"的连通⼦图（也称"极⼤连通⼦图"）。

若无向图为非连通图，则图中各个极大连通子图称为此图的连通分量。

2.1 、那什么是极大连通子图呢？联想到的极小连通子图又是什么呢？

1. 首先先明确两个概念，无向图和有向图；其次，明确一个概念极大连通子图，可以存在于无向图中,也可以存在于有向图中；

2. 但要知道，极小连通子图只存在于连通的无向图中，不存在于不连通的无向图和有向图中。

•  也就是说，极大连通子图和极小连通子图适用条件是不一样的，尽管它们看起来貌似很接近。

无向图中的极大连通子图

无向图中的极大连通子图也叫连通分量。

无向图可以分成两种类型：连通的无向图、不连通的无向图。

•  连通的无向图只有一个极大连通子图，即它本身，因为不存在另一个连通的子图包含的点和边比它本身还要多，所以叫作极大连通子图。

• 不 连通的无向图可以拆分为若干个连通的无向图，如果我们在拆分时注意把能连通的点边都放在一个连通子图中，使这个连通子图足够大，以至于再多包含一个点或边它就变成不连通的了，我们称这个连通子图为极大连通子图，也叫连通分量。

极小连通子图

极小连通子图只存在于连通的无向图中，也就是说该图中只有一个连通分量（极大连通子图），之所以说它极小，是因为极小连通子图只要求包含图中所有顶点及其比顶点数量少一个的边（且不能成环），也就是说如果给极小连通子图任意两个顶点间加入一条边,则必有环。

这里的极大和极小不是指一个意思，不要弄混了，极大连通子图是讨论连通分量的，极小连通子图是讨论生成树的。

下面举几个图例，让大家看看，深入了解一下连通分量：

如图 3 所⽰，虽然图 a 中的⽆向图不是连通图，但可以将其分解为 3 个"最⼤⼦图"（图 b ），它们都满⾜连通图的性质，因此都是连通分量。

看了这么多图例，你学会了吗？能在图中找出连通分量了吗？

需要注意的是，连通分量的提出是以"整个⽆向图不是连通图"为前提的，因为如果⽆向图是连通图，则其⽆法分解出多个最⼤连通⼦图，因为图中所有的顶点之间都是连通的。

三、强连通图

1.  如果一个有向图G，对于其中任意两个顶点v,u，都存在从v到u以及从u到v的有向路径，则称G为强连通图。而在一个不是强连通图的有向图G中，若其中两个顶点u、v在两个方向上都存在有向路径，则称u和v强连通。

2.  强连通图：在有向图中，若任意两个顶点 均连通（一条有向路径），则称该图是强连通图。

3.  有向图中，若任意两个顶点 Vi 和 Vj，满⾜从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有⾄少⼀条通路，则称此有向图为强连通图。如图 4 所⽰就是⼀个强连通图。

四、强连通分量

1. 在有向图中，如果从任意一个顶点出发，都能通过图中的边到达图中的每一个顶点，则称之为强连通图。一张有向图的顶点数 极大的强连通子图 称为强连通分量。

2. 而有向图G的极大强连通子图S，即添加任意顶点都会导致S失去强连通的属性，则称S为G的强连通分量。

3. 强连通分量：有向图中的极大强连通子图。强连通图只有一个强连通分量，即其本身。

4. 与此同时，若有向图本⾝不是强连通图，但其包含的 最⼤连通⼦图具有强连通图的性质，则称该⼦图为强连通分量。整个有向图虽不是强连通图，但其含有两个强连通分量。

”强强“在那里—连通图和强连通图的区别？

• 需求不同：强连通图说的是有向图，连通图说的是无向图。连通图只存在于无向图中，而强连通图通常存在于有向图中。
• 概念不同：
  •  在一幅无向图中，任何两个顶点之间可以相通，则该图就是连通图。
  • 在一幅有向图中，任意两对顶点都可以相通，那么该图就是强连通图。

 可以这样说，连通图是在⽆向图 的基础上对图中顶点之间的连通做了更⾼的要求，⽽强连通图是在有向图 的基础上对图中顶点的连通做了更⾼的要求。

写到最后

❣️四季轮换，已经数不清凋零了多少叶

❣️愿我们往后能向心而行，一路招摇胜！

🐋你的支持认可是我创作的动力

💟创作不易，不妨点赞💚评论❤️收藏💙一下

😘感谢大佬们的支持，欢迎各位前来不吝赐教

想要了解更多吗？没时间解释了，快来点一点！

路遥叶子的博客_CSDN博客-数据结构,安利Java零基础,spring领域博主https://blog.csdn.net/zsy3757486?type=blog

强连通分量

强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。

强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图也可以说，在强连图图的基础上加入一些点和路径，使得当前的图不在强连通，称原来的强连通的部分为强连通分量。

DFS生成树

DFS生成树是根据DFS搜索顺序构成的一颗生成树，形如（自上而下，自左而右）：

有向图的 DFS 生成树主要有 4 种边：
树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
反祖边、反向边（back edge）：示意图中以红色边表示（即7->1 ），也被叫做回边，即指向祖先结点的边。
横叉边（cross edge）：示意图中以蓝色边表示（即 9->7 ），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。
前向边（forward edge）：示意图中以绿色边表示（即 3->6 ），它是在搜索的时候遇到子树中的结点的时候形成的。可以看出树边其实是一个特殊的前向边。

两者联系

考虑 DFS 生成树与强连通分量之间的关系。

如果结点 u 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 u为根的子树中。结点 u被称为这个强连通分量的根。

反证法：假设有个结点 v在该强连通分量中但是不在以 u为根的子树中，那么 u到 v的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 u 是第一个访问的结点矛盾了，命题得证。

Tarjan 算法求强连通分量

在 Tarjan 算法中为每个结点 u维护了以下几个变量：

$df{n}_u$：深度优先搜索遍历时结点 u被搜索的次序。
$lo{w}_u$：能够回溯到的最早的已经在栈中的结点。设以 u为根的子树为$Subtre{e}_u$。$lo{w}_u$ 定义为以下结点的 dfn的最小值：$Subtre{e}_u$中的结点；从$Subtre{e}_u$ 通过一条不在搜索树上的边能到达的结点。
一个结点的子树内结点的 dfn 都大于该结点的 dfn。

从根开始的一条路径上的 dfn 严格递增，low 严格非降。

按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索。在搜索过程中，对于结点 u和与其相邻的结点 v(v 不是u 的父节点）考虑 3 种情况：
v 未被访问：继续对 v进行深度搜索。在回溯过程中，用 $lo{w}_v$更新$lo{w}_u$ 。因为存在从 u 到v 的直接路径，所以 v能够回溯到的已经在栈中的结点，u也一定能够回溯到。
v 被访问过，已经在栈中：根据 low 值的定义，用 $df{n}_v$更新 。
v被访问过，已不在栈中：说明 v已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。
对于一个连通分量图在该连通图中有且仅有一个 u使得$df{n}_u==lo{w}_u$ 。该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 dfn 和 low 值最小，不会被该连通分量中的其他结点所影响。

因此，在回溯的过程中，判定$df{b}_u==lo{w}_u$ 是否成立，如果成立，则栈中 u及其上方的结点构成一个 SCC。

Tarjan算法图示

Tarjan 伪代码与模板

伪代码：

TARJAN_SEARCH(int u)
    vis[u]=true
    low[u]=dfn[u]=++dfncnt
    push u to the stack
    for each (u,v) then do
        if v hasn't been searched then
            TARJAN_SEARCH(v) // 搜索
            low[u]=min(low[u],low[v]) // 回溯
        else if v has been in the stack then
            low[u]=min(low[u],dfn[v])

模板：

// C++ Version
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc;  // 结点 i 所在 SCC 的编号
int sz[N];       // 强连通 i 的大小

void tarjan(int u) {
  low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
  for (int i = h[u]; i; i = e[i].nex) {
    const int &v = e[i].t;
    //未访问，递归遍历
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } //访问过，且在栈中
    else if (in_stack[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
 if(dfn[u]==low[u])
    {
        int y;
        ++scc_cnt;//强连通分量总数+1
        do
        {
            y = stk[top--];//取栈顶元素y
            in_stk[y] = false;//则y不再在栈中
            id[y] = scc_cnt;
            Size[scc_cnt] ++;//第scc_cnt个连通块点数+1
        }while(y!=u);
}

相关题目

受欢迎的牛
每一头牛的愿望就是变成一头最受欢迎的牛。

现在有 N 头牛，编号从 1 到 N，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。

这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。

你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。

输入格式
第一行两个数 N,M；

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

输出格式
输出被除自己之外的所有牛认为是受欢迎的牛的数量。
题解：
先将强联通分量缩点为一个有向无环图（DAG），然后进行拓扑排序，值得注意的是，此时连通分量编号id[]递减的顺序就是topo序了，因为我们++scc_cnt是在dfs完节点i的子节点j后才判断low[u]==dfn[u]后才加的，所以降序来说，前面的节点都是该节点的后继，且该节点的前驱都在自己的前面，那么子节点j如果是强连通分量 scc_idx[j]一定小于scc_idx[i]，当一个强连通的出度为0,则该强连通分量中的所有点都被其他强连通分量的牛欢迎。但假如存在两及以上个出度=0的牛(强连通分量) 则必然有一头牛(强连通分量)不被所有牛欢迎

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = 50010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;//dfs时间戳数组、能够回溯到的最早的已经在栈中的结点，时间戳变量
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!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])//j点未被遍历过
        {
            tarjan(j);//继续dfs 遍历j
            //j也许存在反向边到达比u还高的层,所以用j能到的最小dfn序(最高点)更新u能达到的(最小dfn序)最高点
            low[u] = min(low[u],low[j]);
        }
        //j点在栈中  说明还没出栈 是dfs序比当前点u小的
        //则其 1要么是横插边(左边分支的点)
        //         o
        //        / \
        //       j ← u    
        //     2要么是u的祖宗节点
        //         j
        //      ↗/ 
        //       u    
        //    两种情况u的dfs序都比j大 所以用dfn[j]更新low[u]
        else if(in_stk[j])
        {
            low[u] = min(low[u],dfn[j]);//直接用j的时间戳更新u
        }
        //栈代表当前未被搜完的强连通分量的所有点
    }
    // ⭐
    // 解释一下为什么tarjan完是逆dfs序
    // 假设这里是最高的根节点fa
    // 上面几行中 fa的儿子节点j都已经在它们的递归中走完了下面9行代码
    // 其中就包括 ++scc_cnt 
    // 即递归回溯到高层节点的时候 子节点的scc都求完了
    // 节点越高 scc_id越大
    // 在我们后面想求链路dp的时候又得从更高层往下
    // 所以得for(int i=scc_cnt(根节点所在的scc);i;i--)开始

    // 所以当遍历完u的所有能到的点后 发现u最高能到的点是自己
    // 1 则u为强连通分量中的最高点,则以u为起点往下把该强连通分量所有节点都找出来
    // 2 要么它就没有环,就是一个正常的往下的点
    if(dfn[u]==low[u])
    {
        int y;
        ++scc_cnt;//强连通分量总数+1
        do
        {
            y = stk[top--];//取栈顶元素y
            in_stk[y] = false;//则y不再在栈中
            id[y] = scc_cnt;
            Size[scc_cnt] ++;//第scc_cnt个连通块点数+1
        }while(y!=u);
        //1 因为栈中越高的元素的dfs序越大,那么我们只需要把dfs序比u大的这些pop到u
        //即因为最终会从下至上回到u 所以当y==u     
        //则说明点u所在的所有强连通分量都标记了id
        //           →  u
        //          /  /
        //         /  ne1
        //         ← ne2
        //      因为ne2会在u能到的dfs序里最大的,也就是此时的栈顶
        //      那么我们就逐一pop出ne2和ne1
        //2 要么它就是一个没有环的点 则该点单点成一个连通分量
    }
}

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;
}

参考博客

图论——强连通分量（Tarjan算法)
OIWiki
受欢迎的牛

【定义】

对于一个有向图$G$，其连通分量为：对于分量中任意两点$u,v$，必然可以从$u$走到$v$，且从$v$走到$u$。

强连通分量就是极大连通分量。即一个连通分量加上任何一些点之后它都不是一个连通分量，那么就把它称为强连通分量。

求强连通分量的意义在于能够把任意一个有向图经过缩点之后转化成一个有向无环图（DAG图），缩点是指将所有强连通分量缩成一个点。

【Tarjan算法】

首先我们按DFS序遍历一个图，那么这个图中的所有边可以分为四种：

那么某个点如果在强连通分量中，有以下两种情况：

1. 存在后向边指向其祖先节点；
2. 经过某个横叉边先走到了点$y$，然后点$y$存在前向边走到了某个祖先节点。

在Tarjan算法中我们需要引入一个时间戳的概念，我们按照DFS遍历的顺序给每个结点一个编号，假设为$1\sim N$，那么对于后向边$(x,y)$，$y$的时间戳一定小于$x$，横叉边也是如此。

对于每个点，我们定义两个时间戳：

• $dfn[u]$：表示第一次遍历到$u$时的时间戳；
• $low[u]$：表示从点$u$开始走所能遍历到的最小的时间戳。

那么如果有$dfn[u]==low[u]$，说明点$u$是其所在的强连通分量的最高点。那么我们就可以把$u$所在的这个强连通分量找出来。

【Tarjan算法代码框架】

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;//刚遍历到的时候先初始化当前点的时间戳
    stk.push(u), in_stk[u] = true;//将当前点加到栈中,然后标记这个点在栈中
    for (int i = h[u]; ~i; i = ne[i])//然后遍历u能到的所有邻点
    {
        int j = e[i];
        if (!dfn[j])//如果当前这个点还没被遍历过
        {
            tarjan(j);//遍历一下
            low[u] = min(low[u], low[j]);//儿子能到的最小时间戳u也能到
        }
        else if (in_stk[j])//如果当前这个点还是在栈中
            low[u] = min(low[u], dfn[j]);//那么就用当前点的时间戳更新一下u的low值
    }
    if (dfn[u] == low[u])//如果u为某个强连通分量的最高点
    {
        int t;
        scc_cnt++;//强连通分量的数量
        do
        {
            t = stk.top();
            stk.pop();
            in_stk[t] = false;
            id[t] = scc_cnt;//标记这个点是属于哪个强连通分量
        } while (t != u);
    }
}