拓扑球调
  • 板块学术版
  • 楼主TARGETMINE
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/14 16:05
  • 上次更新2023/11/2 13:53:55
查看原帖
拓扑球调
935263
TARGETMINE楼主2023/10/14 16:05
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int N = 114, M = 514;

int h[N], e[M], nex[M], idx;

int indeg[N];

int vis[N][N];
int vis_s[N];

int n; 

void toposort()
{
	vector<int> res;
	priority_queue<int, vector<int>, greater<int> > Q;
	
	for (int i=1;i<=n;i++)
	{
		if (indeg[i] == 0)
		{
			Q.push(i);
		}
	}
	
	
	while(Q.size())
	{
		int f = Q.top();
		Q.pop();
		res.push_back(f);
		
		for (int i=h[f];i!=-1;i=nex[i])
		{
			int j = e[i];
			indeg[j]--;
			if(indeg[j] == 0)
			{
				Q.push(j);
			}
			
		 } 
	}
	int len = res.size();
	if (len < n)
	{
		cout << n-len;
	}
	else cout << "YES";
	
	
}


void add(int a, int b)
{
	e[idx] = b;
	nex[idx] = h[a];
	h[a] = idx;
	idx++;
}

int main()
{

	cin >> n;
	int a, b, num;
	for (int i=0;i<N;i++)
	{
		h[i] = -1;
	}
	
	for (int i=0;i<n;i++)	
	{
		cin >> a;
		vis_s[a] = 1;
		cin >> num;
		for (int j=0;j<num;j++)
		{
			cin >> b;
			
			vis[a][b] = 1;

		}
	}
	
	for (int i=0;i<N;i++)
	{
		for (int j=0;j<N;j++)
		{
			if (vis_s[j] == 0 || vis_s[i]==0)
			{
				continue;
			}
			if (vis[i][j] == 1)
			{
				add(i, j);
				indeg[j]++;
			}

			
		}
	}
	
	toposort();
	
	
	return 0;
 } 

https://www.luogu.com.cn/problem/P2712

除了一个输出YES的全RE了,球调

2023/10/14 16:05
加载中...