@[dottle](/user/79067) @[小粉兔](/user/10703)
by ttq012 @ 2022-10-19 15:05:33
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int belong[N], odeg[N], ideg[N];
vector <int> z[N];
int dfn[N], low[N], tot, cnt;
bool instk[N];
stack <int> stk;
void dfs(int i)
{
low[i] = dfn[i] = ++ cnt;
instk[i] = true;
stk.push(i);
for (auto &j : z[i])
{
if (!dfn[j])
{
dfs(j);
low[i] = min(low[i], low[j]);
}
else if (instk[j])
low[i] = min(low[i], dfn[j]);
}
if (dfn[i] == low[i])
{
tot ++;
while (stk.top() != i)
{
belong[stk.top()] = tot;
instk[stk.top()] = false;
stk.pop();
}
belong[stk.top()] = tot;
instk[stk.top()] = false;
stk.pop();
}
}
signed main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++)
{
int p;
while (cin >> p, p)
z[i].push_back(p);
}
for (int i = 1; i <= n; i ++)
if (!dfn[i])
dfs(i);
if (tot == 1)
{
cout << "1\n0\n";
return 0;
}
for (int i = 1; i <= n; i ++)
for (auto &j : z[i])
if (belong[i] != belong[j])
odeg[belong[i]] ++, ideg[belong[j]] ++;
int cnt = 0;
for (int i = 1; i <= tot; i ++)
if (!ideg[i])
cnt ++;
cout << cnt << '\n';
int dnt = 0;
for (int i = 1; i <= tot; i ++)
if (!odeg[i])
dnt ++;
cout << max(cnt, dnt) << '\n';
return 0;
}
// 正确代码
```
by ttq012 @ 2022-10-19 15:07:01
@[willem248](/user/378467) done
by feecle6418 @ 2023-02-08 15:16:10