连通分量:
在一个有向图G中的子图中V，对于任意两个点
u
，
v
u，v
u，v来说，如果
u
u
u可以走到
v
v
v，且
v
v
v可以走到
u
u
u的话，我们就称V是一个强连通子图。
强联通分量：
即最大强联通子图（加入任何一个点都会使得当前的强联通子图被破坏）。
求有向图的强联通分量实际上就是一个缩点的过程，如果把所有的强联通分量都视作一个点，建立一个新图的话，我们会发现新图一定是一个DAG图（有向无环图），具有拓扑性。并且拓扑序就是强联通分量按编号降序排列。
Tarjan算法求强联通分量：
模板：
void Tarjan(int u) {
dfn[u] = low[u] = ++ timestamp;
sta[++ top] = u, is_stack[u] = true;
for(int i = h[u]; ~i; i = ne[i]) {
int to = e[i];
if(!dfn[to]) Tarjan(to), low[u] = min(low[u], low[to]);
else if(is_stack[to]) low[u] = min(low[u], dfn[to]);
}
if(low[u] == dfn[u]) {
scc_cnt ++;
int y;
do{
y = sta[top --];
is_stack[y] = false;
id[y] = scc_cnt;
sz[scc_cnt] ++;
}while(y != u);
}
}
例题：
ACwing1174. 受欢迎的牛：
#include <bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
const int N = 1e4 + 100, M = 5e4 + 100;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int h[N], e[M], ne[M], idx, sta[N], top;
int id[N], sz[N], scc_cnt, timestamp, low[N], dfn[N], du[N];
bool is_stack[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;
sta[++ top] = u, is_stack[u] = true;
for(int i = h[u]; ~i; i = ne[i]) {
int to = e[i];
if(!dfn[to]) Tarjan(to), low[u] = min(low[u], low[to]);
else if(is_stack[to]) low[u] = min(low[u], dfn[to]);
}
if(low[u] == dfn[u]) {
scc_cnt ++;
int y;
do{
y = sta[top --];
is_stack[y] = false;
id[y] = scc_cnt;
sz[scc_cnt] ++;
}while(y != u);
}
}
void solve() {
int n, m, a, b;
int ans = 0, zeros = 0;
memset(h, -1, sizeof h);
cin >> n >> m;
while(m --) 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 to = e[j];
a = id[i], b = id[to];
if(a != b)
du[a] ++;
}
for(int i = 1; i <= scc_cnt; ++ i) {
if(!du[i]) zeros ++, ans += sz[i];
if(zeros > 1) {
ans = 0;
break;
}
}
cout << ans << endl;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
IOS;
solve();
return 0;
}
ACwing 367. 学校网络
把题目里问的两个问题转换一下，可以变成这样：
- 第一个问题：有多少个强联通分量的入度为0，即作为起点。
- 第二个问题：先把原图转换成求了强连通分量缩点之后的图，考虑最少加多少条边可以使得这个图变成一个强连通分量。
第一个问题很容易解决，只要求一次强联通分量之后统计每一个强联通分量的入度就可以。
第二个问题需要使用一个结论，具体的证明这里不给出。
结论：设
q
q
q是入度为0的强联通分量（即作为“起点”）的数量，
p
p
p是初读为0的强联通分量（即作为“终点”）的数量。要使得当前图变成一个强联通分量所需要加入的最少边的数量就是
m
a
x
(
q
,
p
)
max(q, p)
max(q,p)。
需要特判当前图已经是一个强联通分量了的情况，这个时候起点的数量是1，终点的数量也是1，但是不用加任何边。
AC code:
#include <bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
const int N = 1e4 + 100, M = 5e4 + 100;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int h[N], e[M], ne[M], idx, sta[N], top;
int id[N], sz[N], scc_cnt, timestamp, low[N], dfn[N], indu[N], outdu[N];
bool is_stack[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;
sta[++ top] = u, is_stack[u] = true;
for(int i = h[u]; ~i; i = ne[i]) {
int to = e[i];
if(!dfn[to]) Tarjan(to), low[u] = min(low[u], low[to]);
else if(is_stack[to]) low[u] = min(low[u], dfn[to]);
}
if(low[u] == dfn[u]) {
scc_cnt ++;
int y;
do{
y = sta[top --];
is_stack[y] = false;
id[y] = scc_cnt;
sz[scc_cnt] ++;
}while(y != u);
}
}
void solve() {
int n, a;
int ans = 0, s = 0, t = 0;
memset(h, -1, sizeof h);
cin >> n;
for(int i = 1; i <= n; ++ i)
while(cin >> a && a != 0) add(i, a);
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 to = e[j];
int x = id[i], y = id[to];
if(x != y) indu[y] ++ , outdu[x] ++;
}
for(int i = 1; i <= scc_cnt; ++ i) {
if(!indu[i]) ans ++, s ++;
if(!outdu[i]) t ++;
}
cout << ans << endl;
if(scc_cnt == 1) cout << 0 << endl;
else cout << max(s, t) << endl;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
IOS;
solve();
return 0;
}
ACwing 1175. 最大半连通子图
首先我们可以发现，对于一个强联通分量来说，从其中任意选出两个点
u
u
u和
v
v
v，
u
u
u和
v
v
v都是一个半联通的点对。
既然我们想要找出最大的半联通子图，那么肯定要尽可能的多选这些半联通的点对，所以我们需要选一整个强联通分量，然后我们会发现，如果一个强联通分量可以走到另一个强联通分量，那么这个强联通分量里的所有点就可以和它能走到的强联通分量里的点构成一个更大的半联通子图。
所以其实我们就是要找出在缩完点之后的图中，点的个数最大的链，这条链就是我们的最大半联通子图。
因为我们发现当我们缩完点之后，整个图变成了一张拓扑图，这样我们所需要求解的就是在拓扑图上求最长路径并且统计最长路径的情况数，由拓扑序进行状态转移就可以，非常简单。
缩完点之后的拓扑序就是强联通分量按编号降序排列。
因为状态只转移一次，所以需要避免重边！！！
AC code：
#include <bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
const int N = 1e5 + 100, M = 2e6 + 100;
const int inf = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> PII;
int h[N], h1[N], e[M], ne[M], idx, top;
int id[N], sz[N], scc_cnt, timestamp, low[N], dfn[N], f[N], g[N];
bool is_stack[N];
int sta[N];
void add(int h[], int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void Tarjan(int u) {
dfn[u] = low[u] = ++ timestamp;
sta[++ top] = u, is_stack[u] = true;
for(int i = h[u]; ~i; i = ne[i]) {
int to = e[i];
if(!dfn[to]) Tarjan(to), low[u] = min(low[u], low[to]);
else if(is_stack[to]) low[u] = min(low[u], dfn[to]);
}
if(low[u] == dfn[u]) {
scc_cnt ++;
int y;
do{
y = sta[top --];
is_stack[y] = false;
id[y] = scc_cnt;
sz[scc_cnt] ++;
}while(y != u);
}
}
void solve() {
int n, m, x;
memset(h, -1, sizeof h);
memset(h1, -1, sizeof h1);
cin >> n >> m >> x;
while(m --) {
int a, b;
cin >> a >> b;
add(h, a, b);
}
for(int i = 1; i <= n; ++ i)
if(!dfn[i]) Tarjan(i);
unordered_set<ll> S;
for(int i = 1; i <= n; ++ i)
for(int j = h[i]; ~j; j = ne[j]) {
int to = e[j], a = id[i], b = id[to];
ll hs = a * 1000000ll + b;
if(a != b && !S.count(hs))
add(h1, a, b), S.insert(hs);
}
for(int i = scc_cnt; i; -- i) {
if(!f[i]) f[i] = sz[i], g[i] = 1;
for(int j = h1[i]; ~j; j = ne[j]) {
int to = e[j];
if(f[to] < f[i] + sz[to]) f[to] = f[i] + sz[to], g[to] = g[i];
else if(f[to] == f[i] + sz[to]) g[to] = (g[to] + g[i]) % x;
}
}
int ans = 0, sum = 0;
for(int i = scc_cnt; i; -- i)
if(ans < f[i]) ans = f[i], sum = g[i];
else if(ans == f[i]) sum = (sum + g[i]) % x;
cout << ans << endl << sum << endl;
}
int main() {
IOS;
solve();
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
