RT 比较震惊,#4-#10TLE????
#include <iostream>
using namespace std;
const int N = 2e2 + 7;
struct Edge {
int to, next;
}edge[N << 2];
int head[N], cnt;
int dfn[N], low[N], ti;
int stck[N], inst;
int n;
bool flag[N];
int ans, tot;
int belong[N], in[N];//belong属于,就是看看当前节点是否属于同一个强联连通分量
//in数组树统计入度
inline void add(int u, int v) {
edge[++ cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
inline int mina(int a, int b) {
if (a < b)
return a;
return b;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ ti;
stck[++ inst] = u;
flag[u] = 1;
for (int i = head[u]; ~i; i = edge[i].next) {
int arrive = edge[i].to;
if (! dfn[arrive]) {
tarjan(arrive);
low[u] = mina(low[u], low[arrive]);
} else if (flag[arrive])
low[u] = mina(low[u], dfn[arrive]);
}
if (dfn[u] == low[u]) {
int cur;
tot ++;
do {
cur = stck[inst --];
flag[cur] = 0;
belong[cur] = tot;//这个点属于当前这个强连通分量内
} while(cur != u);
// cout << endl;
}
return ;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++)
head[i] = -1;
for (int i = 1, people; i <= n; i ++) {
while(1) {
cin >> people;
if (! people)
break;
add(i, people);
}
}
// return 0;
for (int i = 1; i <= n; i ++) {
if (! dfn[i])
tarjan(i);
}
//cout << tot << endl;
for (int i = 1; i <= n; i ++) {
for (int j = head[i]; ~j; j = edge[j].next) {
int arrive = edge[j].to;
if (belong[i] != belong[arrive])//若i这个点能到达arrive这个点,因为我们遍历的是i的出边,但是他们不再同一个强连通分量中,就将入度++
in[belong[arrive]] ++;
}
}
for (int i = 1; i <= tot; i ++) {
if (! in[i])
ans ++;//如果有个强连通分量无入度只能加一个光盘
}
cout << ans << endl;