解题思路
用Tarjan先缩点，缩完点之后得到了一张新的图，在这张新的图上统计入度。只有入度为0的点需要刻一张光盘
附上代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;
const int maxnode =
203, maxedge =
203*
203;
int n, fir[maxnode], nx[maxedge], u[maxedge], v[maxedge], cnt;
int low[maxnode], dfn[maxnode], Index, tot,
in[maxnode], indgr[maxnode], Ans;
bool vis[maxnode];
stack <
int>
S;
inline void addedge(
int x,
int y) {
nx[++cnt] =
fir[x];
fir[x] =
cnt;
u[cnt] = x, v[cnt] =
y;
}
inline void Tarjan(
int x) {
low[x] = dfn[x] = ++
Index;
vis[x] =
1;
S.push(x);
int k =
fir[x];
while (k != -
1) {
if(!
dfn[v[k]]) {
Tarjan(v[k]);
low[x] =
min(low[x], low[v[k]]);
}
else if(vis[v[k]])
low[x] =
min(low[x], dfn[v[k]]);
k =
nx[k];
}
if(dfn[x] ==
low[x]) {
tot++
;
int tmp;
while (!
S.empty()) {
tmp =
S.top();
S.pop();
in[tmp] =
tot;
vis[tmp] =
0;
if(x == tmp)
break;
}
}
}
int main() {
scanf("%d", &
n);
int x;
memset(fir, -
1,
sizeof(fir));
for(
int i=
1; i<=n; i++
) {
while (scanf(
"%d", &x) ==
1) {
if(x ==
0)
break;
addedge(i, x);
}
}
for(
int i=
1; i<=n; i++
) {
if(!
dfn[i]) Tarjan(i);
}
int k;
for(
int i=
1; i<=n; i++
) {
k =
fir[i];
while (k != -
1) {
if(
in[v[k]] !=
in[u[k]])
indgr[in[v[k]]] ++
;
k =
nx[k];
}
}
for(
int i=
1; i<=tot; i++
) {
if(indgr[i] ==
0)
Ans ++
;
}
printf("%d", Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9463836.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
