有向图强连通分量(Tarjan算法)

有向图强连通分量(Tarjan算法)
重要概念(有向图)

重要概念(有向图)

连通分量与强连通分量(SCC)

对于一个有向图,连通分量:对于分量中任意两点 uu, vv, 必然可以从 uu 走到 vv, 且从 vv 走到 uu

强连通分量: 极大连通分量

缩点与有向无环图(DAG) – 拓扑图

缩点就是将一堆点变成一个点,然后为他们再次建立索引

DAGDAG 是有向无环图又称为拓扑图,字面意思就是没有环的有向图,因为其必然存在拓扑序,所以也成为拓扑图

有向图和DAG的关系:

有向图缩点变成有向无环图

几个边

四种边

  • 树枝边:任意两个节点之间的有向边都是树枝边
  • 前向边:从dfs序列的前面的点指向后面的点,比如图中从y到x
  • 后向边:从dfs序列后面的点指向前面的点,比如图中从x到y(假设都是有边的)
  • 横叉边:从当前点指向左边的点,如图中的 xxzz,这个 zz 一定是已经被遍历过的点,这也是为什么说是左边的点,不能够是右边的点

当前点是否存在于 SCCSCC 中?有两种情况:

  • 情况1:存在后向边指向祖先节点
  • 情况2:先走到横叉边,横叉边再走到祖先

时间戳

引入两个时间戳,时间戳就是dfs遍历的顺序,那么比较容易思考得到:
树枝边/前向边的 yy 的时间戳大于 xx ,而后向边/横叉边的 yy 的时间戳小于 xx

Tarjan算法求解强连通分量(SCC)

对每个点定义两个时间戳:

  • dfn[n]dfn[n] 表示遍历到 uu 的时间戳
  • low[u]low[u]uu 开始走,所能遍历到的最小时间戳是什么

uu 是其所在的强连通分量的最高点,等价于: dfn[u]==low[u]dfn[u] == low[u]

考虑时间戳的更新问题:
low更新的方法

模板代码:

int h[maxn], e[maxn], ne[maxn], idx; void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx++; } // stack用于记录暂时存储遍历到的点(如果是强连通分量的话就可以直接回溯找到整个分量~~),但是不是dfs的那个stack stack<int > stk; // 定义的两个时间戳dfn, low int dfn[maxn], low[maxn]; // 表示是否在栈中,用于更新low,后面会看到 bool in_stk[maxn]; // 记录强连通分量的id,也就是缩点操作,对整个分量建立索引 int id[maxn]; // 时间戳 int timestamp; // 记录有多少个强连通分量 int scc_cnt; 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]){ int y = e[i]; // 两种更新low的情况 if(!dfn[y]) { // 对于没有计算过的点,递归求解邻点的情况 Tarjan(y); // 同时更新当前点 low[u] = min(low[u], low[y]); }else if(in_stk[y]) low[u] = min(low[u], dfn[y]); } // u是其所在强连通分量的最高点的等价条件,这个时候开始记录这个分量 if(low[u] == dfn[u]){ // y用于遍历整个强连通分量 int y; // 强连通分量的个数 + 1 ++scc_cnt; do { // stack中记录了分量,直接不断的弹出即可 y = stk.top(); stk.pop(); // 出栈更新in_stk数组 in_stk[y] = false; // 记录当前点所对应缩点之后的点的索引,创建原图与缩图后的索引映射 id[y] = scc_cnt; }while(y != u); // 直到到达u位置为止 } }

题目

1174. 受欢迎的牛

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

现在有 NN 头牛,编号从 11NN, 给你 MM 对整数 (A,B)(A,B), 表示牛 AA 认为牛 BB 受欢迎。

这种关系是具有传递性的,如果 AA 认为 BB 受欢迎, BB 认为 CC 受欢迎,那么牛 AA 也认为牛 CC 受欢迎。

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

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

接下来 MM 行,每行两个数 A,BA, B, 意思是 AA 认为 BB 是受欢迎的(给出的信息有可能重复,即有可能出现多个 A,BA, B )。

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

数据范围
1N1041≤N≤10^4
1M5×1041≤M≤5×10^4

输入样例

3 3 1 2 2 1 2 3

输出样例

1

样例解释
只有第三头牛被除自己之外的所有牛认为是受欢迎的。

分析:
TarjanTarjan 算法求解强连通分量的模板题目
题目意思是给定了一些牛之间的受欢迎关系,并且有一种关系就是如果牛 bb 受牛 aa 欢迎, 牛 cc 受牛 bb 欢迎, 那么牛 cc 也同样受牛 aa 的欢迎,也就是欢迎具有传递的效果,现在问的是有多少个牛是受所有牛欢迎的

首先可以肯定的是如果给定的这个图中有两个终点的话,必然是 nn :

两个终点的问题 - 牛

对于任意一个点,不可能同时受这两个终点的欢迎。因为任意一个点只有两种情况:

  • 非这两个终点:因为图中的两个点是终点,因此不存在从这两个终点出发的到非终点的路径的
  • 这两个终点中的其中一个(具有等价的效果,仅仅分析一个即可):同样的和第一个原因相同,必然不存在另外一个终点出发达到当前点的路径

然后考虑这个题目答案只能是 0011 吗?
不是,必然是一个类终点(后面会解释),但是答案可能很大,因为存在环:

牛多种解的情况

再扩展一下,也就是强连通分量

那么其实就可以将图中的强联通分量全部缩点,那么原来的图就变成了 DAGDAG

对于 DAGDAG 图而言,这个问题就好办了,统计出度为 00 的点的个数即可,如果为 11,则加上末尾的点的个数(也就是对应原图中的点的个数,因为可能是一个分量的缩点)就是答案,如果 >1> 1的话就是 00, 也就是说有多个类终点(缩点后的图中的终点),对应原图中也是多个终点

AC代码:

#include <bits/stdc++.h> using namespace std; using ll = long long; inline int sd(int &n) { return scanf("%d", &n); } inline int sld(ll &n) { return scanf("%lld", &n); } const int inf = 0x3f3f3f3f; const int maxn = 1e6 + 6; int n, m; int h[maxn], e[maxn], ne[maxn], idx; void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx++; } int dfn[maxn], low[maxn], timestamp; stack<int > stk; bool in_stk[maxn]; int scc_cnt; int id[maxn]; int dout[maxn]; int Size[maxn]; void Tarjan(int u){ stk.push(u), in_stk[u] = true; dfn[u] = low[u] = ++timestamp; for(int i = h[u];~i;i = ne[i]){ int y = e[i]; if(!dfn[y]){ Tarjan(y); low[u] = min(low[u], low[y]); }else if(in_stk[y]) low[u] = min(low[u], dfn[u]); } if(dfn[u] == low[u]){ int y; ++scc_cnt; do { y = stk.top(); stk.pop(); id[y] = scc_cnt; in_stk[y] = false; Size[scc_cnt]++; }while(y != u); } } int main(){ memset(h, -1, sizeof h); sd(n), sd(m); for(int i = 0;i < m;++i){ int a, b; sd(a), sd(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 y = e[j]; int a = id[i], b = id[y]; if(a != b) dout[a]++; } } int zeros = 0, res = 0; for(int i = 1;i <= scc_cnt;++i){ if(!dout[i]){ zeros++; res += Size[i]; if(zeros > 1){ sum = 0; break; } } } cout << res << endl; return 0; }

3+

发表评论

电子邮件地址不会被公开。 必填项已用*标注

10 − 6 =