神犇求助!!!!万绿丛中一点红
  • 板块P2244 选举预测
  • 楼主bobzbh
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/1/16 10:18
  • 上次更新2023/10/24 04:02:45
查看原帖
神犇求助!!!!万绿丛中一点红
111349
bobzbh楼主2023/1/16 10:18
//做法参照第二篇题解 
#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/16 10:18
加载中...