牛客网考研机试题集合:图的连通分支数

2023-12-28 18:08

本文主要是介绍牛客网考研机试题集合:图的连通分支数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这里注意图的序号标记是任意的,不是0~n 或1~n;只含有输入的顶点

题目缺少信息!顶点的个数要足够大 ,至少1000010

考点:并查集

也可以使用DFS或BFS

#include<bits/stdc++.h>
using namespace std;
const int MAXSIZE=1000010;int father[MAXSIZE],mark[MAXSIZE];
int findRoot(int x);
int main() {int a,b;fill(father,father+MAXSIZE,-1);set<int> s;while(cin>>a>>b) {s.insert(a);s.insert(b);int fa=findRoot(a);int fb=findRoot(b);if(fa!=fb) {father[fa]=fb;}}int cnt=0;for(auto it=s.begin(); it!=s.end(); it++) {if(father[*it]==-1) {cnt++;}}cout<<cnt<<endl;return 0;
}
int findRoot(int x) {if(father[x]==-1) {return x;} else {int tmp=findRoot(father[x]);father[x]=tmp;return tmp;}
}

 

这篇关于牛客网考研机试题集合:图的连通分支数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/546806

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

Java基础回顾系列-第六天-Java集合

Java基础回顾系列-第六天-Java集合 集合概述数组的弊端集合框架的优点Java集合关系图集合框架体系图java.util.Collection接口 List集合java.util.List接口java.util.ArrayListjava.util.LinkedListjava.util.Vector Set集合java.util.Set接口java.util.HashSetjava

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

java集合的概述

集合就是一个容器,我们可以把多个对象放入的容器中。就像水杯(假设容量可以不断扩大)一样,你可以往水杯中不断地添加水,既然是水杯,你就不能往里添加沙子,也就是说集合中添加的对象必须是同一个类型的(引用类型,而不能是基本类型)。 看到集合的介绍会让我们的想起数组,那么集合和数组有什么区别呢? 首先,数组的大小是固定的,而集合理论上大小是不限的。 其次,数组既可以存储基本数据类型的数据,也可以存储

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比

【中等】保研/考研408机试-二分查找(模板题)

二分查找就是在一个有序数组中查找某个值,以首端尾端的中点mid查找对比,mid与要查找的数进行对比,看落在哪个区间,在那个区间重新得到首端和尾端,进而得到新的mid值。 一、模板题 二分查找-I_牛客题霸_牛客网 class Solution {public:int search(vector<int>& nums, int target) {int left=0,right=nums.s