HDU1232 畅通project 并查集
project 查集 畅通
2023-09-14 09:08:59 时间
这道题跟HDU 1213 How Many Tables 并查集很接近,都是赤裸裸的并查集的题。
思路:如果还须要建n-1条路。每并一次就自减1。
參考代码:
#include<stdio.h> int fa[1000]; int find(int u) { return fa[u]==u?u:fa[u]=find(fa[u]); } int main() { int i,n,m,u,v,x,y; scanf("%d%d",&n,&m); while (n) { for (i=1;i<=n;i++) fa[i]=i; for (i=1;i<=m;i++) { scanf("%d%d",&u,&v); x=find(u);y=find(v); if (x!=y) { fa[x]=y; n--; } } n--; printf("%d\n",n); scanf("%d%d",&n,&m); } return 0; }
优化:先用数组储存m组数,然后仅仅对这些节点的根节点
赋初值fa[u[i]]=u[i];fa[v[i]]=v[i];
參考代码:
#include<stdio.h> int fa[1000],u[1000],v[1000]; int find(int u) { return fa[u]==u?u:fa[u]=find(fa[u]); } int main() { int i,n,m,x,y; scanf("%d%d",&n,&m); while (n) { for (i=1;i<=m;i++) { scanf("%d%d",&u[i],&v[i]); fa[u[i]]=u[i]; fa[v[i]]=v[i]; } for (i=1;i<=m;i++) { x=find(u[i]);y=find(v[i]); if (x!=y) { fa[x]=y; n--; } } n--; printf("%d\n",n); scanf("%d%d",&n,&m); } return 0; }
相关文章
- 记一个mvn奇怪错误: Archive for required library: 'D:/mvn/repos/junit/junit/3.8.1/junit-3.8.1.jar' in project 'xxx' cannot be read or is not a valid ZIP file
- spring boot:创建一个简单的web(maven web project)
- [Ember] Creating Your First Ember.js Project with Ember-CLI
- Fiori 应用通过 Adaptation Project 的增强方式分享
- our reuse project in HCP
- SAP WebIDE 里 UI5 应用的隐藏文件 project.json
- how to resolve 404 not found error for sap-ui-core.js after project is cloned to
- Try to create new xs project in AG3
- Eclipse里看到project 存在向上或者向下的箭头
- 关于 SAP SEGW Project Type 的四种不同类型
- 搭建Dynamic Web Project(动态web项目)的springmvc工程1
- Dubbo分布式服务框架入门(附project)
- ACM-最小生成树之畅通project——hdu1863
- 前端project师,确定你的目标吧!无能的人才管他叫命运
- DescriptionResourcePathLocationType Project configuration is not up-to-date with pom.xml. Select: Maven->Update Project... from the project context menu or use Quick Fix.spark-MTline 1Maven Co
- :app:checkDebugAarMetadata Your project has set `android.useAndroidX=true`, but configuration `:app: