第十个点,题解代码算出有1236个强连通分量,我的算出了1237。正确输出为1236 1236,我的输出为1235 1235
#include <bits/stdc++.h>
#define short int
using namespace std;
const short MAXN = 10500;
short n, n2, it;//n2为强连通分量个数
bool t[MAXN][MAXN];
short l[MAXN];//即low
short d[MAXN];//即dfn
bool In[MAXN], Out[MAXN];
bool b[MAXN];//是否在栈内
bool v[MAXN];//是否完成计算过
short f[MAXN];//属于哪个强连通分量
stack <short> s;
void tar(short &x)
{
d[x] = l[x] = ++it;
s.push(x);
b[x] = 1;
for (short i = 1; i <= n; i++)
if (t[x][i] && !v[i])//是否为横叉边
if (b[i])//是否为后向边或前向边
l[x] = min(d[i], l[x]);
else//树边
{
tar(i);
l[x] = min(l[x], l[i]);
}
if (d[x] == l[x])
{
n2++;
while (s.top() != x)
b[s.top()] = 0, f[s.top()] = n2, s.pop();
b[x] = 0;
s.pop();
f[x] = n2;
}
v[x] = 1;
}
int main()
{
//freopen("P2812_10.in", "r", stdin);
short b;
cin >> n;
for (short i = 1; i <= n; i++)
{
cin >> b;
while (b)
{
t[i][b] = 1;
cin >> b;
}
}
for (short i = 1; i <= n; i++)
if (! v[i])
tar(i);
//cout << n2 << endl;
for (short i = 1; i <= n; i++)
for (short j = 1; j <= n; j++)
if (f[i] != f[j])
In[f[j]] |= t[i][j],
Out[f[i]] |= t[i][j];
short in = 0, out = 0;
for (int i = 1; i <= n2; i++)
in += ! In[i],
out += ! Out[i];
cout << in << endl;
if (n2 > 1)
cout << max(in, out) << endl;
else
cout << 0 <<endl;
return 0;
}