算法1
(Floyd + 并查集) $O(n^3)$
这道题就像y总讲的一样,由于数据很小,直接拿传递闭包加并查集也可以写缩图。看没人写这样的题解就写了一个。运行时间其实和tarjan的时间差不多,30ms左右
C++ 代码
// Created by Henry Yi
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int e[N][N], d[N][N];
int f[N];
int din[N], dout[N];
int find(int x) {
if (f[x] != x) f[x] = find(f[x]);
return f[x];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
f[i] = i;
int j;
while (scanf("%d", &j), j) {
e[i][j] = 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (e[i][k] && e[k][j]) {
e[i][j] = 1;
}
}
if (e[i][j] && e[j][i]) {
f[find(i)] = find(j);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (find(i) != find(j) && e[i][j] && !d[find(i)][find(j)]) {
d[find(i)][find(j)] = 1, din[find(j)]++, dout[find(i)]++;
}
}
}
int p = 0, q = 0;
bool flag = true;
for (int i = 1; i <= n; i++) {
if (i == f[i]) {
if (!din[i]) p++;
if (!dout[i]) q++;
}
if (find(i) != find(1)) flag = false;
}
printf("%d\n", p);
if (flag) puts("0");
else printf("%d\n", max(p, q));
return 0;
}