如下,tarjan
模板,样例输出 5 \n 5
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int head[N], cnt = 0;
struct Edge {
int to, next;
} e[N * N];
int n, m, dfn[N], low[N], si[N], co[N], de[N], num = 0, col = 0;
int bok[N][3], in[N], out[N];
inline void add(int u, int v) {
e[++ cnt].to = v;
e[cnt].to = head[u];
head[u] = cnt;
}
int st[N], top = 1;
inline void tarjan(int u) {
dfn[u] = low[u] = ++ num;
st[top ++] = u;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(dfn[v] == 0) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if(co[v] == 0) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
++ col;
while(st[top] != u) {
top --;
co[st[top]] = col;
}
top --;
}
return ;
}
int main() {
scanf("%d", &n);
int k = 0;
for (int a = 1, b; a <= n; ++ a) {
scanf("%d", &b);
while(b != 0) {
add(a, b);
bok[++ k][1] = a;
bok[k][2] = b;
scanf("%d", &b);
}
}
for (int i = 1; i <= n; ++ i) {
if(!dfn[i]) tarjan(i);
}
for (int i = 1; i <= k; ++ i) { // 统计入度和出度
if(co[bok[i][1]] != co[bok[i][2]]) {//同种颜色不需要统计
out[co[bok[i][1]]] ++;
in[co[bok[i][2]]] ++;
}
}
int s1 = 0, s2 = 0;
for (int i = 1; i <= col; ++ i) {
if(in[i] == 0) s1 ++;
if(out[i] == 0) s2 ++;
}
printf("%d\n%d\n", s1, max(s1, s2));
return 0;
}
求助,谢谢了!!!