思路 并查集找到联通块的个数，答案就是联通块个数减一。 因为这是无向图，所以就不用dfs跑个数了，直接裸的并查集就好了 如果没有学过并查集可以去看看这篇博客，这位大佬写的巨详细 那就直接上代码了 代码 #include<bits/stdc++.h>
using namespace std
展开全文
题目链接：https://ac.nowcoder.com/acm/problem/14685看题目好像是图论？ 不存在的 ，吓唬你一下而已。这就是简单的并查集，用到的也是并查集最常规的find 和merge（合并） 操作而已在并查集基础上我用了集合，将各个不同的区域网放入了集合中，可能用不着set，
展开全文
明说是图，实际是并查集 题意是根据结点和边得个数可以得到图的个数，答案就是 （图的个数 - 1 ）根据样例 #include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int f[maxn];
int
展开全文
题目链接：https://ac.nowcoder.com/acm/problem/14685思路：这道题是一个简单的并查集，只需要找出连通数的个数，然后对连通数的个数减去1就可以得到答案。 #include<iostream>
using namespace std;
int fa[1
展开全文
并查集的裸体问加几条边可以使图中的点两两到达就是使图成为连通图也就是说所有点的根节点都指向一个点用数组p[j]记录j节点的根节点也就是说对于所有的点 有且仅有一个点的 p[i]=i， 也就是唯一的父亲节点 如果有两个就说明图中有两个连通块 也就是需要 一条边取联通这两个块以此类推代码 #includ
展开全文
并查集 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 给你一个 n 个点，m 条边的无向图，求至少要在这个的基础上加多少条无向边使得任意两个点可达~ 输入描述
展开全文
思路 我们知道，要让n个点联通，就要用n-1条边。Kruskal求最小生成树用到的边数num，那么缺的边数就是n-1-num。 代码 #include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct E{
展开全文
一道并查集题，找出连通块个数，并用连通块数减一即得最小添加边数。
using namespace std;
const int mm=1e5+5;
int n,m,a,b,p[mm],ans;
int find(int x){//找祖宗节点
if(p[x]==x) return x;
展开全文
include<bits/stdc++.h> using namespace std;int f[100010];void into(int x){ for(int i=0;i<x;i++) f[i]=i;}int find(int x){ if(x!=f
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
