ZOJ4109 Welcome Party(2019浙江省赛)
2024-10-08 11:22:34
并查集算连通块的数量,集合的个数就是必然不开心的人数,再跑bfs,用优先队列维护~
#include<bits/stdc++.h> using namespace std; ; vector<int> g[maxn]; int father[maxn]; int N,M,T; int isRoot[maxn]; int visit[maxn]; int findfather (int x) { int a=x; while (x!=father[x]) x=father[x]; while (a!=father[a]) { int z=a; a=father[a]; father[z]=x; } return x; } void Union (int a,int b) { int faA=findfather (a); int faB=findfather (b); if (faA<faB) swap(faA,faB); father[faA]=faB; } int main () { scanf ("%d",&T); while (T--) { scanf ("%d %d",&N,&M); ;i<=N;i++) father[i]=i,visit[i]=,isRoot[i]=; ;i<=N;i++) g[i].clear(); int x,y; ;i<M;i++) { scanf ("%d %d",&x,&y); g[x].push_back(y); g[y].push_back(x); Union (x,y); } ;i<=N;i++) isRoot[findfather(i)]++; ; priority_queue<int,vector<int>,greater<int>> q; ;i<=N;i++) { if (isRoot[i]) { ans++; visit[i]=; q.push(i); } } printf ("%d\n",ans); while (!q.empty()) { int u=q.top(); q.pop(); printf ("%d",u); ;i<g[u].size();i++) ; if (!q.empty()) printf (" "); } printf ("\n"); } ; }
最新文章
- 偏移:translate ,旋转:rotate,缩放 scale,不知道什么东东:lineCap 实例
- phpMyAdmin如何设置float小数点
- hibernate-聚合函数分组统计数据查询
- Lotus 迁移到Exchange 2010 POC 之在Exchange 2007安装Transport Suite!
- 关于XShell的常见使用和设置以及Linux中的常见命令.
- 结构性产品 Structured Product
- 解决VTune错误.../lib64/libstdc++.so.6: version `GLIBCXX_3.4.14&;#39; not found (required by ...)
- 解决因特网和xshell考虑到问题
- 使用Jax-rs 开发RESTfull API 入门
- VB中的GDI编程-2 画笔
- 开源Spring解决方案--lm.solution
- Appium--入门demo
- [Bash]LeetCode192. 统计词频 | Word Frequency
- SpringBoot(十四)-- 整合Swagger2
- Python爬虫实战四之抓取淘宝MM照片
- idea开发工具安装说明
- hashlib 和loggin模块
- php中各种http报错的状态码分析
- mysql用触发器同步表
- 【Leetcode】【Medium】Combination Sum