求求,万绿丛中一点红
  • 板块P2244 选举预测
  • 楼主bobzbh
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/1/12 21:53
  • 上次更新2023/10/24 04:31:27
查看原帖
求求,万绿丛中一点红
111349
bobzbh楼主2023/1/12 21:53
//做法参照第二篇题解 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#define N 1000086
using namespace std;
vector<int> pic[N];
queue<int> que;
bool ans[N];
int main()
{
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(false);
	int n,maxn=0;
	vector<int> start;
	cin>>n;
	for(int i=1; i<=n; ++i)
	{
		int k;
		cin>>k;
		//邻接表存储有向边指向弱的一方 
		if(k>maxn)
		{
			maxn=k;
			start.clear();
			start.push_back(i);
		}
		if(k==maxn)
		{
			start.push_back(i);
		}
		for(int j=1; j<=k; ++j)
		{ 
			int lose;
			cin>>lose;
			pic[i].push_back(lose);
		}
	}
	for(int i=0; i<start.size(); ++i)
	{
		//加入初度最多的点 
		que.push(start[i]);
		ans[start[i]]=1;
	}
	while(!que.empty())
	{
		int now=que.front();
		while(!que.empty())
		{
			que.pop();
		}
		//通过加入当前节点无法一次性到达的节点来完成广搜的拓展操作
		//正确性证明见第二篇题解 
		for(int i=1; i<=n; ++i)
		{
			if(ans[i]==0&&find(pic[now].begin(),pic[now].end(),i)==pic[now].end())
			{
				ans[i]=1;
				que.push(i);
			}
		}
	}
	vector<int> out;
	//统计答案 
	for(int i=1; i<=n; ++i)
	{
		if(ans[i]==1)
		{
			out.push_back(i);
		}
	}
	cout<<out.size()<<" ";
	for(int i=0; i<out.size(); ++i)
	{
		cout<<out[i]<<" ";
	}
	return 0;
}
//时间复杂度有待提高,但吸口氧T的点都能过掉
2023/1/12 21:53
加载中...