首先找出图中的强连通分量,用tarjan算法。强连通分量内部强联通,所以将其看成一个点是不影响的。
进行缩点之后,整张图变成了一个有向无环图。
首先对于每一条边进行检测,如果这一条边是连接两个团的,那么更新这两个团的出入度。这里我们知道,出度总和等于入度总和。
接下来再对于每个团遍历,如果这个团出度为0或入度为0,就需要统计,最后需要添加的母机个数就是入度为0的个数,因为入度为零的团没有别的团连接,无法使用母机;需要加的边数就是整个图出度为0和入度为0的较大值,这一问其实是让缩成的DAG变成一个强连通图,强连通图的性质是没有出度为0或入度为0。这个问题想的还不是很透彻,悬而未决。
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
vector<int>e[N];
bitset<N>instk;
stack<int>stk;
int dfn[N], low[N], tot;
int scc[N], cnt;
int deg_in[N], deg_out[N];
int n;
void tarjan(int u)
{
dfn[u] = low[u] = ++tot;
stk.push(u);
instk[u] = 1;
for (int v : e[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
cnt++;
int v;
do {
v = stk.top();
stk.pop();
instk[v] = 0;
scc[v] = cnt;
} while (v != u);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1, a; i <= n; i++) {
while (scanf("%d", &a) && a != 0) {
e[i].push_back(a);
}
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i);
}
}
for (int i = 1; i <= n; i++) {
for (int v : e[i]) {
if (scc[v] != scc[i]) {
deg_out[scc[i]] ++;
deg_in[scc[v]] ++;
}
}
}
int a = 0, b = 0;
for (int i = 1; i <= cnt; i++) {
if (!deg_in[i]) a++;
if (!deg_out[i]) b++;
}
printf("%d\n", a);
if (cnt == 1) {
printf("0\n");
} else {
printf("%d\n", max(a, b));
}
return 0;
}
标签:缩点,连通,Network,int,入度,USACO,dfn,low
From: https://www.cnblogs.com/CYLSY/p/17084954.html