ACwing367.学校网络(tarjanDAG有向图的强联通分量

添加链接描述

#include
using namespace std;
const int N&＃61;110,M&＃61;1e4&＃43;10;
int h[N],ne[M],e[M],idx,n;
void add(int a,int b){e[idx]&＃61;b,ne[idx]&＃61;h[a],h[a]&＃61;idx&＃43;&＃43;;
}
int dfn[N],low[N],ssc_cnt,id[N],timestamp,in_stack[N],size_scc[N];
stack<int>st;
void tarjan(int u){dfn[u]&＃61;low[u]&＃61;&＃43;&＃43;timestamp;st.push(u),in_stack[u]&＃61;true;for(int i&＃61;h[u];~i;i&＃61;ne[i]){int j&＃61;e[i];if(!dfn[j]){tarjan(j);low[u]&＃61;min(low[u],low[j]);}else if(in_stack[j]){low[u]&＃61;min(low[u],dfn[j]);}}if(dfn[u]&＃61;&＃61;low[u]){int j;&＃43;&＃43;ssc_cnt;do{j&＃61;st.top();st.pop();in_stack[j]&＃61;0;id[j]&＃61;ssc_cnt;size_scc[ssc_cnt]&＃43;&＃43;;}while(u!&＃61;j);}
}
int din[N],dout[N];
int main(){cin>>n;memset(h,-1,sizeof h);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){int x;while(cin>>x,x){add(i,x);}}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(!dfn[i]){tarjan(i);}}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;h[i];~j;j&＃61;ne[j]){int k&＃61;e[j];int a&＃61;id[i],b&＃61;id[k];if(a!&＃61;b){dout[a]&＃43;&＃43;;din[b]&＃43;&＃43;;}}}int ans1&＃61;0,ans2&＃61;0;for(int i&＃61;1;i<&＃61;ssc_cnt;i&＃43;&＃43;){//遍历的是缩点后的DAG的联通分量数目if(!din[i])ans1&＃43;&＃43;;if(!dout[i])ans2&＃43;&＃43;;}cout<<ans1<<endl;if(ssc_cnt&＃61;&＃61;1)printf("0");else cout<<max(ans1,ans2)<<endl;return 0;
}