首页 > 其他分享 >计蒜客:修建大桥(并查集/DFS/BFS)

计蒜客:修建大桥(并查集/DFS/BFS)

时间:2024-11-01 19:19:31浏览次数:1  
标签:parent int graph 查集 DFS BFS rooty 1005 find

 找到有几张连通图即可解决问题。

DFS:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 int graph[1005][1005] = {0};
 5 bool visited[1005] = {false};
 6 void dfs(int p) {
 7     if (visited[p]) {
 8         return;
 9     }
10     visited[p] = true;
11     for (int i = 1; i <= n; ++i) {
12         if (graph[p][i] == 1)
13             dfs(i);
14     }
15 }
16 int main() {
17     cin >> n >> m;
18     while (m--) {
19         int s, e;
20         cin >> s >> e;
21         graph[s][e] = 1;
22         graph[e][s] = 1;
23     }
24     int cnt = 0;
25     dfs(1);
26     while(1) {
27         bool isconnected = true;
28         for (int i = 2; i <= n; ++i) {
29             if (!visited[i]) {
30                 isconnected = false;
31                 dfs(i);
32                 cnt++;
33                 break;
34             }
35         }
36         if (isconnected) {
37             cout << cnt;
38             break;
39         }
40     }
41 }

并查集:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 vector<int> parent(1005);
 5 int find(int x) {
 6     if (parent[x] == x) {
 7         return x;
 8     }
 9     return find(parent[x]);
10 }
11 void merge(int x, int y) {
12     int rootx = find(x);
13     int rooty = find(y);
14     if (rootx != rooty) {
15         parent[rootx] = rooty;
16     }
17 }
18 
19 int main() {
20     cin >> n >> m;
21     for (int i = 1; i <= n; ++ i) {
22         parent[i] = i;
23     }
24     while (m--) {
25         int s, e;
26         cin >> s >> e;
27         merge(s, e);
28     }
29     set<int> roots;
30     for (int i = 1; i <= n; ++ i) {
31         roots.insert(find(i));
32     }
33     cout << roots.size() - 1;
34 }

 

标签:parent,int,graph,查集,DFS,BFS,rooty,1005,find
From: https://www.cnblogs.com/coderhrz/p/18521108

相关文章

  • gofastdfs
    私有化目前部署了3台,如189.22,部署在/data/godfs启动进程 fileserver数据存储 files配置文件 conf日志log Nginx部署在189.10,路径:/etc/nginx转发配置nginx.conf及 conf.d下的文件nginx.conf中包含了全局的配置,如http块等conf.d下的文件包含各个转发的配置g......
  • BFS(Breath First Search 广度优先搜索)
    @目录一、知识及框架二、案例说明案例1:使用bfs计算二叉树的最小高度案例2:解开密码锁的最少次数,要求:请写一个算法,初始状态为0000,拨出target的最少次数,其中避免出现deadends中的包含的任意一个死亡密码,如果永远无法拨出target,则返回-1本人其他文章链接一、知识及框架BFS算法都是......
  • 算法-并查集
    1.寻找图中是否存在路径(LeetCode1971)有一个具有n个顶点的双向图,其中每个顶点标记从0到n-1(包含0和n-1)。图中的边用一个二维整数数组edges表示,其中edges[i]=[ui,vi]表示顶点ui和顶点vi之间的双向边。每个顶点对由最多一条边连接,并且没有顶点存在与......
  • 【并查集】【中间值范围】NOIP2017]奶酪
    https://ac.nowcoder.com/acm/contest/22904/1027开了ll还见祖宗注意x^2+y2算完之后先判断有没有超4r2的范围,没有的话再计算z^2,算是对longlong溢出的特判#include<bits/stdc++.h>typedeflonglongll;usingnamespacestd;classUnionFind{public:UnionFind(ll......
  • 每日OJ题_牛客_AB20走迷宫_BFS_C++_Java
    目录牛客_AB20走迷宫_BFS题目解析C++代码Java代码牛客_AB20走迷宫_BFS走迷宫_牛客题霸_牛客网(nowcoder.com)描述:        给定一个n×m的网格,在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。网格中的一些格子上放置有障碍物,放有......
  • 【寻迹#4】并查集
    并查集一、并查集并查集是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素。顾名思义,并查集支持两种操作:合并(Union):合并两个元素所属集合(合并对应的树)查询(Find):查询某个元素所属集合(查询对应的树的根节点),这可以用于判......
  • 并查集
    并查集并查集是一种数据结构,它主要处理一些不相交集合的合并问题。一些常见的用途有求连通子图、最小生成树Kruskal算法和求公共祖先等。并查集的主要操作有:初始化Init查询Find合并Union初始化Init()voidInit(intn){vector<int>father(n+1);//创......
  • 经典算法思想--并查集
    前言 (最近在学习Java,所有函数都是用Java语言来书写的)前言部分是一些前提储备知识在并查集(Union-Find)数据结构中,rank(中文称为“秩”)是用来表示树的高度或深度的一种辅助信息。它的主要作用是优化合并操作,以保持并查集的结构尽可能扁平,从而提高查询效率。秩的具体定义......
  • 深度优先算法(DFS)洛谷P1683-入门
    虽然洛谷是有题解的,但是你如果直接看得懂题解,你也不会来看这篇文章..这些代码均是我记录自身成长的记录,有写的不好的地方请谅解!先上代码:#include<iostream>#include<vector>#include<iomanip>#include<cstdio>usingnamespacestd;constintN=30;charg[N......
  • CF771A. Bear and Friendship Condition 题解 并查集
    题目链接:https://codeforces.com/problemset/problem/771/A视频讲解:https://www.bilibili.com/video/BV1tZ1FYPELp/?p=6题目大意:判断一个无向图中的每个连通块是否都是一个完全图。首先我们可以用并查集维护每个连通块的大小。其次,我们可以开一个\(cnt_i\)表示以节点\(i\)......