#include <string.h> #include<iostream> #include <stdio.h> const int V = 105; const int E = 1005; const int inf = 0x3f3f3f3f; using namespace std; struct edge { int to, next; } Edge[E]; int head[V], e, n, m; int indeg[V], outdeg[V]; //点的入度和出度数 int belong[V], low[V], dfn[V], scc, cnt;//dfn[]:遍历到u点的时间; low[]:u点可到达的各点中最小的dfn[v] int S[V], top; bool vis[V];//v是否在栈中 bool cut[V]; int addedge(int u, int v) { Edge[e].to = v; Edge[e].next = head[u]; head[u] = e++; return 0; } //int cont = 0; void tarjan(int u) { int v; dfn[u] = low[u] = ++cnt; S[top++] = u; vis[u] = true; for (int i=head[u]; i!=-1; i=Edge[i].next) { v = Edge[i].to; if (dfn[v] == 0) { //v点未遍历 tarjan(v); low[u] = low[u] < low[v] ? low[u] : low[v];//回溯保证low为所联系的最小值 } else if (vis[v] && low[u] > dfn[v])//v在栈中，修改low[u] low[u] = dfn[v]; } if (dfn[u] == low[u]){//u为该强连通分量中遍历所成树的根 缩点 ++scc; do{ v = S[--top];//栈中所有到u的点都属于该强连通分量，退栈 vis[v] = false; belong[v] = scc; } while (u != v); } } int solve() { scc = top = cnt = 0; memset(dfn, 0, sizeof(dfn)); memset(vis, false, sizeof(vis)); for (int u=1; u<=n; ++u) if (dfn[u] == 0) tarjan(u); return scc; } void CountDegree() { memset(indeg, 0, sizeof(indeg)); memset(outdeg, 0, sizeof(outdeg)); for (int u=1; u<=n; ++u) for (int i=head[u]; i!=-1; i=Edge[i].next){ int v = Edge[i].to; if (belong[u] != belong[v]){ indeg[belong[v]]++; outdeg[belong[u]]++; } } } int main() { int u, v, i; while (~scanf("%d", &n)) { memset(cut, false, sizeof(cut)); e = 0; memset(head, -1, sizeof(head)); for(int i=1; i<=n; i++) { while(scanf("%d",&v) && v!=0) { addedge(i, v); } } int cutn = 0; int in = 0, out = 0; solve(); if (scc == 1) printf("1\n0\n"); else{ CountDegree(); in = 0, out = 0; for (int i=1; i<=scc; ++i){ if (indeg[i] == 0) in++; if (outdeg[i] == 0) out++; } } if(scc != 1) printf("%d\n%d\n", in, (in > out ? in : out)); } return 0; }
