校园网络【[USACO]Network of Schools加强版】
题目链接:luogu P2812
题目大意
有一个有向图,问你两个问题。
第一个,至少要选多少个点,使得从这些点出发可以到达所有点。
第二个,问你至少要加多少边,使得整个图之间任意两个点都可以互相到达。
思路
这道题其实和原来的做法是一样的。
因为 Tarjan 算法复杂度是 O ( n + m ) O(n+m) O(n+m),所以在这里仍然能过。
代码
#include<cstdio>
#include<iostream>
using namespace std;
struct node {
int to, nxt;
}e[5000001];
int n, le[10001], KK, x, tmp, num;
int dfn[10001], low[10001], n_n, kuai[10001];
int sta[10001], in[10001], sum[10001];
int ru[10001], chu[10001], ans1, ans2;
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
}
void tarjan(int now) {
dfn[now] = low[now] = ++tmp;
sta[++sta[0]] = now;
for (int i = le[now]; i; i = e[i].nxt)
if (!dfn[e[i].to]) {
tarjan(e[i].to);
low[now] = min(low[now], low[e[i].to]);
}
else if (!in[e[i].to]) low[now] = min(low[now], low[e[i].to]);
if (dfn[now] == low[now]) {
in[now] = ++n_n;
sum[n_n] = 1;
while (sta[sta[0]] != now) {
in[sta[sta[0]]] = n_n;
sum[n_n]++;
sta[0]--;
}
sta[0]--;
}
return ;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
while (x) {
add(i, x);
scanf("%d", &x);
}
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++)
for (int j = le[i]; j; j = e[j].nxt)
if (in[i] != in[e[j].to]) {
chu[in[i]]++;
ru[in[e[j].to]]++;
}
for (int i = 1; i <= n_n; i++) {
if (!ru[i]) ans1++;
if (!chu[i]) ans2++;
}
if (n_n == 1) printf("1\n0");
else printf("%d\n%d", ans1, max(ans1, ans2));
return 0;
}