题解：模板题，dijkstra或spfa算法，代码略
题解：模板题，floyd算法，代码略
题解：反向建边，令稳定节点为红色，不稳定节点黑色。对于每个节点，维护一个from值，含义为该节点可追溯到的红色节点。红色节点from值为其自身，黑色节点若有至少两个可追溯到的红色节点，则记为0;一个节点为红色节点，当且仅当其父亲为0节点或其from值为其自身。先将0节点的邻接节点染为红色，然后删除0节点，将这些节点入队。根据拓扑序，维护队列中节点的儿子的入度和from值，直到染色结束。红色节点个数即为所求。
代码：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<queue> 5 using namespace std; 6 #define MAXN 100005 7 struct Edge{ 8 int to,next; 9 }edge[MAXN*15]; 10 int n,tot=0,last[MAXN]={},in[MAXN]={}; 11 void add_edge(int a,int b){ 12 ++tot; 13 edge[tot].to=b; 14 edge[tot].next=last[a]; 15 last[a]=tot; 16 in[b]++; 17 } 18 int from[MAXN],color[MAXN]={}; 19 void toposort(){ 20 queue<int> que; 21 memset(from,-1,sizeof(from)); 22 for(int i=last[0];i;i=edge[i].next){ 23 in[edge[i].to]=0; 24 que.push(edge[i].to); 25 color[edge[i].to]=1; 26 from[edge[i].to]=edge[i].to; 27 } 28 while(!que.empty()){ 29 int x=que.front(); que.pop(); 30 for(int i=last[x];i;i=edge[i].next){ 31 if(color[edge[i].to]==0){ 32 if(from[edge[i].to]==-1) 33 from[edge[i].to]=(color[x]?x:from[x]); 34 else if(from[edge[i].to]&&from[edge[i].to]!=(color[x]?x:from[x])) 35 from[edge[i].to]=edge[i].to; 36 if(from[edge[i].to]==edge[i].to) 37 color[edge[i].to]=1; 38 } 39 if(--in[edge[i].to]==0) 40 que.push(edge[i].to); 41 } 42 } 43 } 44 int main(){ 45 scanf("%d",&n); 46 for(int i=1;i<=n;i++){ 47 int k; 48 scanf("%d",&k); 49 for(int j=1;j<=k;j++){ 50 int x; 51 scanf("%d",&x); 52 add_edge(x,i); 53 } 54 } 55 toposort(); 56 int ans=0; 57 for(int i=1;i<=n;i++) 58 if(color[i]) 59 ans++; 60 printf("%d ",ans); 61 return 0; 62 }