算法提高课-图论-有向图的强连通分量-AcWing 367. 学校网络:强连通分量、tarjan算法

本文主要是介绍算法提高课-图论-有向图的强连通分量-AcWing 367. 学校网络:强连通分量、tarjan算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- - 题目解答
  - 题目来源

题目解答

在这里插入图片描述

来源：acwing

分析：

第一问：通过tarjan算法求出强连通分量并且缩点后，统计入度为0的点的个数p即可。

第二问，至少加几条边才能使图变成强连通分量？这个答案是max（p,q）。含义是入度为0，和出度为0的点的个数的最大值。但特例是，如果只有1个强连通分量，那么不需要加边，直接输出0即可。

第二问的问题实际上是：对于任意一个有向无环图，至少加多少条边，才能使之变成强连通分量？记入度为0的点个数是p，出度为0的点的个数为q。

答案是max(p, q). 证明过程可以自行搜索。

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

ac代码


#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 10010;
int n;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt;
int din[N], 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] = ++ ts;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]){int y;++ scc_cnt;do{y = stk[top --];in_stk[y]  = false;id[y] = scc_cnt;}while(y != u);}
}int main(){cin >> n;memset(h, -1, sizeof h);for(int i = 1; i <= n; i ++){int t;while(cin >> t, t) add(i, t);}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){dout[a] ++, din[b] ++;}}}int a = 0, b = 0;// 遍历每个强连通分量,统计缩点后的点的入度和出度for(int i =  1; i <= scc_cnt; i ++){if(!din[i]) a ++;if(!dout[i]) b++;}cout << a << endl;// 只有1个强连通分量，不需要加边if(scc_cnt == 1) cout << 0 << endl;else  cout << max(a, b) << endl;
}