WA第十个点,c++有注释
查看原帖
WA第十个点,c++有注释
1122193
FarmerDrone楼主2024/7/27 14:53

第十个点,题解代码算出有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;
} 
2024/7/27 14:53
加载中...