1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
|
#include <algorithm> #include <cstring> #include <stack> using namespace std; int n,u[5001000],v[5001000],w[5001000],fir[10100],nxt[5001000],cnt; void (int ui,int vi){ ++cnt; u[cnt]=ui; v[cnt]=vi; nxt[cnt]=fir[ui]; fir[ui]=cnt; } stack<int> S; int dfn[10100],low[10100],vis[10100],dfs_clock=0,scccnt=0,sccno[10100]; void tarjan(int u){ dfn[u]=low[u]=++dfs_clock; S.push(u); vis[u]=true; for(int i=fir[u];i;i=nxt[i]){ if(!dfn[v[i]]){ tarjan(v[i]); low[u]=min(low[u],low[v[i]]); } else if(vis[v[i]]) low[u]=min(low[u],dfn[v[i]]); } if(dfn[u]==low[u]){ ++scccnt; while(1){ int x=S.top(); S.pop(); vis[x]=false; sccno[x]=scccnt; if(x==u) break; } } } int in[10100],out[10100],ans1=0,ans2=0; void sd(void){ for(int i=1;i<=cnt;i++) if(sccno[u[i]]!=sccno[v[i]]) in[sccno[v[i]]]++,out[sccno[u[i]]]++; for(int i=1;i<=scccnt;i++){ if(!in[i]) ++ans1; if(!out[i]) ++ans2; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int a; scanf("%d",&a); while(a!=0){ if(i==a) continue; addedge(i,a); scanf("%d",&a); } } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); sd(); printf("%dn%d",ans1,ans2); return 0; }
|
近期评论