【刷题】Serval and Essay
2022/9/14 23:18:39
本文主要是介绍【刷题】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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-15Springboot应用的多环境打包学习
- 2024-10-15Springboot应用的生产发布学习
- 2024-10-15创建Springboot项目学习:新手入门教程
- 2024-10-15创建springboot项目学习:新手入门教程
- 2024-10-14Java创业学习:新手入门教程
- 2024-10-14JAVA创业学习:新手入门教程
- 2024-10-14Java创业学习:从零开始的Java编程教程
- 2024-10-14Java对接阿里云智能语音服务学习
- 2024-10-14JAVA对接阿里云智能语音服务学习教程
- 2024-10-14Java副业学习:从入门到实战的简单教程