首页 / 算法 / 数据结构与算法问题 朋友圈
数据结构与算法问题 朋友圈
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法问题 朋友圈,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1375字,纯文字阅读大概需要2分钟。
内容图文
![数据结构与算法问题 朋友圈](/upload/InfoBanner/zyjiaocheng/1334/cda590d4a3ae4b7193ff6d63a6e0a2b5.jpg)
-
假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友...),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。
假如:n = 5 , m = 3 , r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈,结果为2个朋友圈。
奈何能力不够,用欧拉回路DFS解题,但是Memory Limit Exceed了,晚上回来再学用并查集。
题目描述:
- 输入:
-
输入包含多个测试用例,每个测试用例的第一行包含两个正整数 n、m,1=<n,m<=100000。接下来有m行,每行分别输入两个人的编号f,t(1=<f,t<=n),表示f和t是好友。 当n为0时,输入结束,该用例不被处理。
- 输出:
-
对应每个测试用例,输出在这n个人里一共有多少个朋友圈。
- 样例输入:
-
5 3 1 2 2 3 4 5 3 3 1 2 1 3 2 3 0
样例输出:
2
1
#include <iostream> using namespace std; int n, m,j; int G[10000][10000]; int du[100000]; bool visit[100000]; void DFS(int start,int & counts) { for (int i = 1; i <= n; i++) { if (!visit[i] && G[start][i]) { counts++; visit[i] = true; DFS(i,counts); } } } int main() { int x1,x2; while (cin >> n&&n != 0) { int counts = 0, num = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) G[i][j] = 0; for (int i = 1; i <=n; i++) { du[i] = 0; visit[i] = false; } cin >> m; for (int i = 0; i <m; i++) { cin >> x1 >> x2; G[x1][x2] = 1; G[x2][x1] = 1; du[x1]++; du[x2]++; } visit[1] = true; counts++; while (counts != n) { for (int i = 1; i <= n; i++) { j = counts; DFS(i, counts); if (counts > j) { num++; } } } cout << num << endl; } return 0; }
原文:http://blog.csdn.net/leviathan_/article/details/39293185
内容总结
以上是互联网集市为您收集整理的数据结构与算法问题 朋友圈全部内容,希望文章能够帮你解决数据结构与算法问题 朋友圈所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。