算法提高课-图论-有向图的强连通分量-AcWing 1174. 受欢迎的牛:tarjan算法求强连通分量、tarjan算法板子、强连通图

文章目录

• • • 题目解答
    • 题目来源

题目解答

来源：acwing

分析：

强连通图：给定一张有向图。若对于图中任意两个结点x，y，既存在从x到y的路径，也存在从y到x的路径，则称该有向图是“强连通图”。

强连通分量(SCC)指的是强连通图的极大连通子图（点最多的）。

说人话，强连通分量中任意两点都存在边，再加入任何别的点，它都不再是连通分量。

或者说，对于一张有向图，强连通分量就是任意两点都有路径(x能到y, y也能到x)，并且包含点最多的图。

有向图的强连通分量有什么用呢？

主要是通过缩点（将强连通分量缩成一个点），把有向图，转换为有向无环图（拓扑图，DAG）。

如下图，左图圈内的是一个强连通分量，通过缩点，转化为右图。这种做法其实有很多应用，比如求最短路等。

需要知道的几个概念：

树枝边(x,y)
x是y的父节点，x到y的边称为树枝边

前向边(x,y)
x是y的祖先节点，x到y的边称为前向边。
树枝边是特殊的前向边。

后向边(y,x)
x是y的祖先节点，y到x的边称为后向边。

横叉边（x，y）
在对有向图进行dfs遍历时，x是已经搜过的图的分支（不是前向边），现在在搜的点是y，y到x的有向边是横叉边。

tarjin算法求强连通分量

引入时间戳的概念：在dfs遍历的过程中，按照每个结点第一次被访问的时间顺序，依次给予图中N个结点1~N的整数标记，该标记被称为时间戳，记为dfn[x].

对每个点定义两个时间戳：
dfn[u]表示遍历到u的时间戳；

low[u] 表示从u开始走（遍历它的子树），所能遍历到的最小时间戳是什么。

我们在求强连通分量的时候，求的是每个强连通分量最上面的那个点。

u是所在的强连通分量的最高点，等价于dfn[u]== low[u]，因为low[u]表示的是从u开始能够遍历到的最小的时间戳，正好等于自己的时间戳，说明什么？ 说明u就是这个连通分量的最高点啊！

tarjan算法求强连通分量的模板

背模板的思路

/* 1. 加时间戳； 2. 放入栈中，做好标记； 3. 遍历邻点1）如果没遍历过，tarjan一遍，用low[j]更新最小值low2) 如果在栈中，用dfn[j]更新最小值low 4.找到最高点1）scc个数++2）do-while循环：从栈中取出每个元素；标志为出栈；对元素做好属于哪个scc；该scc中点的数量++ */

具体模板代码

// tarjan 算法求强连通分量 // 时间复杂度O(n+ m) 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所能遍历到的时间戳的最小值low[u] = min(low[u], low[j]);}// 如果当前点在栈中//注意栈中存的可能是树中几个不同分支的点,因为有横叉边存在// 栈中存的所有点，是还没搜完的点，同时都不是强连通分量的最高点// 这里表示当前强连通分量还没有遍历完，即栈中有值else if(in_stk[j])//更新一下u点所能到的最小的时间戳//此时j要么是u的祖先，要么是横叉边的点，时间戳小于ulow[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[scc_cnt] ++;} while(y != u);} }

对于本题的解析：

题意是找到被其他所有牛都欢迎的牛的数量。在有向图的角度，就是所有的点都可以走到当前这个点。

如果暴力做的话，对于每个点都要dfs或者bfs，看是否所有点都可以到达该点，做一遍的时间复杂度是O（n + m），那么n个点，时间复杂度是O(n(n+m)),这里的n是1w，m是5
w，时间限制是1s，会超时。

优化的解法：

如果是拓扑图（有向无环图）的话，就好解决了。为什么呢？只需要统计出度为0的点的数量。如果出度为0的点的数量大于等于2，那么一定不存在最受欢迎的牛（其他所有点都有边连到该点）。
这是因为是有向无环图，如果有2个或以上的点出度为0，那么其中1个叶子结点必然有到不了的点，也就是不存在最受欢迎的牛。这个需要画图理解一下。

如果只存在一个出度为0的点呢？

综上，如果是拓扑图的话，这道题就好做了。实际上，我们可以用强连通分量算法将图转换为拓扑图！

先求出该图的强连通分量，然后缩点，变成有向无环图。找到出度为0的点的数量为1的情况，然后统计该点所表示的强连通分量，其中包含多少个点，这里的所有点都可以被其他所有点走到。

ac代码

#include<bits/stdc++.h> using namespace std;const int N = 10010, M = 50010;int n, m; int h[N], w[M], e[M], ne[M], idx; // 邻接表一套 // dfn[u] 存的是遍历到u的时间戳 // low[u]存的是从u出发，遍历子树，所能遍历到的最小的时间戳 //timestamp 就是时间戳 int dfn[N], low[N], timestamp; int stk[N], top; // 栈，和栈顶元素索引 bool in_stk[N]; // 是否在栈中 //id[u]表示u的强连通分量的编号，scc_cnt表示强连通分量的编号 // size_scc[u]表示编号为u强连通分量中点的数量 int id[N], scc_cnt, size_scc[N]; int dout[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;//遍历u点的所有邻点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; //y元素所属的连通块编号size_scc[scc_cnt] ++; //该连通块内包含的点数}while(y != u); // 直到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; j = ne[j]){int k = e[j];int a = id[i]; //a表示i所在连通分量的编号int b = id[k]; // b表示k所在连通分量的编号//如果点i和点k不在同一个连通块// dout存的是出度，因为本题只需要出度//在其他题目中，可能是要建边，因为这里是构造有向无环图if(a != b) dout[a] ++; // 从a走到b，a的出度++}}// 和本题有关的部分：// zeros是统计在新图中，出度为0的点的个数// sum表示满足条件的点（最受欢迎的奶牛）的个数int zeros = 0, sum = 0;for(int i = 1; i <= scc_cnt; i ++){if(!dout[i]){zeros ++;sum += size_scc[i];if(zeros > 1){sum = 0;break;}}}cout << sum << endl; }

题目来源

https://www.acwing.com/problem/content/1176/

总结

以上是生活随笔为你收集整理的算法提高课-图论-有向图的强连通分量-AcWing 1174. 受欢迎的牛:tarjan算法求强连通分量、tarjan算法板子、强连通图的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。