描述某市计划建设一个通信系统。按照规划这个系统包含若干端点这些端点由通信线缆链接。消息可以在任何一个端点产生并且只能通过线缆传送。每个端点接收消息后会将消息传送到与其相连的端点除了那个消息发送过来的端点。如果某个端点是产生消息的端点那么消息将被传送到与其相连的每一个端点。为了提高传送效率和节约资源要求当消息在某个端点生成后其余各个端点均能接收到消息并且每个端点均不会重复收到消息。现给你通信系统的描
解题思路:
- 首先,判断输入是否结束,即判断N和M是否都为0,如果是,则结束程序;
- 对于每组输入,首先创建一个邻接矩阵adj[][],用于表示每两个端点之间是否有通信线缆相连;
- 遍历所有端点,对于每个端点i,进行广度优先搜索(BFS),判断从端点i出发能否遍历到所有其他端点;
- 在BFS过程中,使用一个visited数组记录已经访问过的端点,初始化为false;
- 对于每个端点i,将visited[i]置为true,并将i加入到一个队列中;
- 当队列不为空时,取出队首端点j,并遍历与端点j相连的所有端点k;
- 如果端点k还未被访问过,则将visited[k]置为true,并将k加入到队列中;
- 遍历完所有相连端点后,如果visited数组中仍有false值,说明存在无法遍历到的端点,输出No;
- 如果visited数组中所有值均为true,则说明从端点i出发可以遍历到所有其他端点,输出Yes;
- 继续下一组输入,重复步骤1。
具体实现见下方代码:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1005;
int main() {
int N, M;
while (cin >> N >> M && (N != 0 || M != 0)) {
vector<vector<bool>> adj(N + 1, vector<bool>(N + 1, false));
for (int i = 0; i < M; i++) {
int A, B;
cin >> A >> B;
adj[A][B] = adj[B][A] = true;
}
bool is_possible = false;
for (int i = 1; i <= N; i++) {
vector<bool> visited(N + 1, false);
queue<int> q;
visited[i] = true;
q.push(i);
while (!q.empty()) {
int j = q.front();
q.pop();
for (int k = 1; k <= N; k++) {
if (adj[j][k] && !visited[k]) {
visited[k] = true;
q.push(k);
}
}
}
bool all_visited = true;
for (int k = 1; k <= N; k++) {
if (!visited[k]) {
all_visited = false;
break;
}
}
if (all_visited) {
is_possible = true;
break;
}
}
if (is_possible) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
``
原文地址: https://www.cveoy.top/t/topic/iSia 著作权归作者所有。请勿转载和采集!