本文主要是介绍南邮 OJ 1131 谣言传播，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
谣言传播
时间限制(普通/Java) : 4000 MS/ 12000 MS 运行内存限制 : 65536 KByte
总提交 : 633 测试通过 : 198
总提交 : 633 测试通过 : 198
比赛描述
知道“人言可畏”吗？在我们的生活中，尤其在现有的网络上，存在一些广泛传播的谣言。今天我们在一个群体中研究这个问题：
（1）一个群体中存在一些两两之间的朋友关系；
（2）一个人发布“谣言”；
（3）一个人在知道“谣言”时，会告诉他（她）的朋友；
请你判断是否所有人最终都知道谣言。
输入
第一行是一个正整数：测试用例数目，最多为100。之后，每个测试用例包括多行：
l 第1行给出两个整数（空格分隔），前者表示群体人数n，后者表示“谣言”发布者t，群体成员用整数序号表示，2≤n≤200，0≤t≤n-1
l 第2行给出一个整数，群体两两存在的朋友关系数m，0≤m≤20100
l m行，每行两个整数（空格分隔），表示群体中两个成员存在朋友关系。
输出
对于每个测试用例:
l 所有人最终都知道谣言则输出“Yes”，否则输出“No”
注意：输出部分的结尾要求包含一个多余的空行。
样例输入
2
3 0
2
0 1
0 2
4 0
2
0 1
2 3
样例输出
Yes
No
题目来源
算法与数据结构设计考核赛2009
#include<iostream>
#include<queue>
#define N 200
using namespace std;int main(){bool friends[N][N];bool vst[N];int T,n,t,m,i,j,cnt;queue<int> q;cin>>T;while(T--){memset(friends,0,sizeof(friends));memset(vst,0,sizeof(vst));cin>>n>>t>>m;while(m--){cin>>i>>j;friends[i][j] = 1;friends[j][i] = 1;}q.push(t);vst[t] = 1;cnt = 1;while(!q.empty()){i = q.front();q.pop();for(j=0;j<n;++j){if(friends[i][j] && !vst[j]){q.push(j);vst[j] = 1;++cnt;}}}if(cnt == n){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}
}
这篇关于南邮 OJ 1131 谣言传播的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
