【刷题】Serval and Essay

本文主要是介绍【刷题】Serval and Essay，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目地址：J-Serval and Essay_"蔚来杯"2022牛客暑期多校训练营1 (nowcoder.com)
题意：
　　有一张n个点m条边的无重边无自环的有向图
　　初始时可以选择一个点染黑，其余点均为白色
　　若某个点的所有边的起点都是黑点，则该点可以被染黑
　　最大化图中黑点的数量
　　多组数据，n <= 2e5 m <= 2e5

题型：启发式合并

代码以及注释：

#include<bits/stdc++.h>
using namespace std;

//点的合并：
//    将所有入度为1的点与他的前驱合并 
//    然后反复合并

const int N=2e5+10;
int n,m;
set <int > fr[N],to[N];
int fa[N],sz[N]; 

struct node
{ int a,b; };

int find(int x)     //类似于并查集的点集合并 
{
    if(x != fa[x] ) return fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y ) return;
    //启发式合并的本质：将size小的合并到size大的上 
    if(to[x].size() > to[y].size() )
        swap(x,y);
    
    //将x合并到y上 
    fa[x]=y; 
    sz[y] += sz[x];
    vector <node > v;
    
    //使用增强for的方法，遍历set 
    for(int now : to[x])
    {
        to[y].insert(now);
        fr[now].insert(y);
        fr[now].erase(x);
        
        if(fr[now].size()==1 )
             v.push_back(node{now,y});
    }
    
    int v_size=v.size(); 
    for(int i=0;i<v_size;i++)
        merge(v[i].a,v[i].b);
}

void clear_and_input()
{
    scanf("%d",&n);
    
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        sz[i]=1;
        to[i].clear();
        fr[i].clear();
    }
    
    for(int i=1;i<=n;i++)
    {
        int k,x;
        scanf("%d",&k);
        while(k--)
        {
            scanf("%d",&x);     //添加x到i的一条边 
            to[x].insert(i);
            fr[i].insert(x);
        }
    }
}

void suodian()
{
    for(int i=1;i<=n;i++)
    {
         if(fr[i].size() == 1 )
         {    
             //从set中取出元素！！！ 
             int x = *fr[i].begin() , y=i;
            merge(x,y);
        }
    }
}

void count()
{
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,sz[i]); 
    printf("%d\n",ans);
} 

int main()
{
    int T,cas=0;
    cin>>T;
    while(T--)
    {
         clear_and_input();
         suodian();
         printf("Case #%d:",++cas);
         count();
    }
    
    return 0;
} 

PS：bitset实际上是若干个long long连接实现的，不过是位运算较快

PS：使用增强for的方式遍历set

set <node > s;

for(node now : s )

这篇关于【刷题】Serval and Essay的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！