刻录光盘--和炸铁路，tarjan

https://www.luogu.com.cn/problem/P2835

多做多看多想，一切都会水到渠成

受欢迎的牛--tarjan缩点+图论出度-CSDN博客

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<ll,int> pii;
int n,m; 
vector<int> mp[N];
int low[N],dfn[N],ne[N];
int cnt,c;
stack<int> st;
map<int,int> in;
map<int,int> an;
map<int,int> w;
void tarjan(int x)///tarjan板子 
{low[x]=dfn[x]=++cnt;st.push(x);for(int a:mp[x]){if(!dfn[a]){tarjan(a);low[x]=min(low[x],low[a]);}else if(!ne[a]){low[x]=min(low[x],low[a]);}}if(low[x]==dfn[x]){ne[x]=++c;while(st.top()!=x){ne[st.top()]=c;///ne是强连通分量数组 st.pop();}st.pop();//an这个map来统计强连通分量c里面的点数 }
}
ll ann;
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){int y;while(cin>>y&&y){mp[i].push_back(y);}}for(int i=1;i<=n;i++){if(!dfn[i]){tarjan(i);}}for(int i=1;i<=n;i++){for(int a:mp[i]){if(ne[a]!=ne[i]){in[ne[a]]++;}}}for(int i=1;i<=c;i++){if(!in[i]) ann++;}cout<<ann;return 0;
}