80wa求助
  • 板块P2712 摄像头
  • 楼主Javie
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/7 20:02
  • 上次更新2023/11/2 15:01:13
查看原帖
80wa求助
867819
Javie楼主2023/10/7 20:02

有点儿离谱,简简单单的拓扑排序一时半会儿找不出来哪里出了问题,请各路大神帮我看看:

#include <bits/stdc++.h>
typedef long long ll;
typedef double db;
#define mem(a, b) memset(a, b, sizeof a)
#define F1(i, a, b) for (int i = (a); i <= (b); i++)
#define F2(i, a, b) for (int i = (a); i < (b); i++)
#define F3(i, a, b) for (int i = (a); i >= (b); i--)
#define F4(i, a, b) for (int i = (a); i > (b); i--)
#define mod 233333
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 2e5 + 7;
int n, x, m, y;
int in[MAXN];
int e[MAXN], ne[MAXN], idx, h[MAXN], a[MAXN], ans;
vector<int> l;
bool vis[MAXN];
void add(int a, int b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
	in[b]++;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	queue<int> q;
	cin >> n;
	mem(h, -1);
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i] >> m;
		vis[a[i]]=true;
		for (int j = 0; j < m; j++)
		{
			cin >> y;
			add(a[i], y);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (!in[a[i]]) q.push(a[i]);
	}
	while (!q.empty())
	{
		ans++;
		auto t = q.front();
		q.pop();
		for (int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i];
			in[j]--;
			if (!in[j]&&vis[a[i]])
				q.push(j);
		}
	}
	if (ans == n)
		cout << "YES" << endl;
	else
		cout << n - ans+1;
	return 0;
}

2023/10/7 20:02
加载中...