谋鬼 2022-02-27 09:04 采纳率: 100%
浏览 32
已结题

跨海大桥c++ 没想明白

【题目描述】
人鱼王国在某些岛屿之间修建了跨海大桥,这样多个岛屿就可以组成一块大陆,交通也更加方便了!
不过国王的命令依然无法传达给公民,这让国王感觉非常苦恼,所以国王想要请悟空帮忙给各个岛屿传递一个消息。
虽然人鱼王国不大,但是如果悟空每个岛屿都去一次,就会耽误很长时间,影响取经大业;
所以悟空决定先计算一下,通过桥的连接,人鱼王国的岛屿可以组成多少块大陆。
【输入格式】
第一行包含两个正整数N和M,N表示有几个岛屿,M表示有几座跨海大桥;
接下来有M行,每行两个数字u和v,用空格隔开,表示编号为u的和v的岛屿之间有一座桥相连。
【输出格式】
一个正整数,表示人鱼王国的岛屿可以组成多少块大陆
【样例输入1】
5 4
1 2
2 3
1 3
4 5
【样例输出1】
2
【样例解释1】
如下图所示:
1-2
| /
3

4--5

通过桥的连接,可以组成两块大陆;
第一块大陆由{1,2,3}这三个岛屿组成,第二块大陆由{4,5}这两个岛屿组成。

【样例输入2】
5 2
1 2
2 3
【样例输出2】
3
【样例解释2】
如下图所示:
1--2--3
4
5
通过桥的连接,可以组成三块大陆;
第一块大陆由{1,2,3}这三个岛屿组成,第四个岛屿、第五个岛屿分别自成一块大陆

【数据范围】
对于100%的数据:1<=N<=100,1<=M<=5000;每座桥都是双向通路,且(u,v)不会重复

  • 写回答

1条回答 默认 最新

  • [PE]经典八炮 2022-02-27 09:15
    关注

    用并查集。。。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 3月7日
  • 已采纳回答 2月27日
  • 创建了问题 2月27日

悬赏问题

  • ¥15 stm32代码移植没反应
  • ¥15 matlab基于pde算法图像修复,为什么只能对示例图像有效
  • ¥100 连续两帧图像高速减法
  • ¥15 组策略中的计算机配置策略无法下发
  • ¥15 如何绘制动力学系统的相图
  • ¥15 对接wps接口实现获取元数据
  • ¥20 给自己本科IT专业毕业的妹m找个实习工作
  • ¥15 用友U8:向一个无法连接的网络尝试了一个套接字操作,如何解决?
  • ¥30 我的代码按理说完成了模型的搭建、训练、验证测试等工作(标签-网络|关键词-变化检测)
  • ¥50 mac mini外接显示器 画质字体模糊