通信系统判断：是否满足消息传递要求？

{"title":"通信系统判断：是否满足消息传递要求？", "description":"本题要求判断一个通信系统是否满足以下要求：每个端点均能接收到消息，且每个端点均不会重复收到消息。输入包含系统描述，判断是否符合要求，并输出Yes或No。", "keywords":"通信系统, 消息传递, 算法, 孤立节点, 环路, C++", "content":""解题思路：\n1. 首先判断是否存在孤立节点，即某个节点没有与其他节点相连的线缆。如果存在孤立节点，则肯定不符合要求，输出"No"。\n2. 然后判断是否存在环路，即是否存在从某个节点出发可以经过若干线缆回到该节点的路径。如果存在环路，则肯定不符合要求，输出"No"。\n3. 如果以上两个条件都不满足，则输出"Yes"。\n\n代码实现：\nc++\n#include <iostream>\n#include <vector>\n#include <queue>\nusing namespace std;\n\nbool isConnected(vector<vector<int>>& graph, int N) {\n vector<bool> visited(N + 1, false); // 用于记录节点是否被访问过\n queue<int> q; // 用于广度优先搜索\n q.push(1); // 从节点 1 开始搜索\n visited[1] = true; // 将节点 1 标记为已访问\n while (!q.empty()) {\n int current = q.front(); // 取出队列首元素\n q.pop(); // 从队列中移除首元素\n for (int neighbor : graph[current]) { // 遍历当前节点的邻居节点\n if (!visited[neighbor]) { // 如果邻居节点未被访问过\n q.push(neighbor); // 将邻居节点加入队列\n visited[neighbor] = true; // 将邻居节点标记为已访问\n }\n }\n }\n for (int i = 1; i <= N; ++i) { // 检查所有节点是否都被访问过\n if (!visited[i]) { // 如果有节点未被访问过，则说明存在孤立节点\n return false; // 返回 false\n }\n }\n return true; // 所有节点都被访问过，说明图是连通的\n}\n\nbool hasCycle(vector<vector<int>>& graph, int N) {\n vector<bool> visited(N + 1, false); // 用于记录节点是否被访问过\n vector<bool> onStack(N + 1, false); // 用于记录节点是否在递归调用栈上\n for (int i = 1; i <= N; ++i) { // 遍历所有节点\n if (!visited[i]) { // 如果节点未被访问过，则从该节点开始进行深度优先搜索\n if (dfs(graph, i, visited, onStack)) { // 如果存在环路，则返回 true\n return true; // 返回 true\n }\n }\n }\n return false; // 没有找到环路，返回 false\n}\n\nbool dfs(vector<vector<int>>& graph, int node, vector<bool>& visited, vector<bool>& onStack) {\n visited[node] = true; // 将节点标记为已访问\n onStack[node] = true; // 将节点标记为在递归调用栈上\n for (int neighbor : graph[node]) { // 遍历当前节点的邻居节点\n if (!visited[neighbor]) { // 如果邻居节点未被访问过，则进行递归调用\n if (dfs(graph, neighbor, visited, onStack)) { // 如果递归调用返回 true，则说明存在环路\n return true; // 返回 true\n }\n } else if (onStack[neighbor]) { // 如果邻居节点在递归调用栈上，则说明存在环路\n return true; // 返回 true\n }\n }\n onStack[node] = false; // 将节点标记为不在递归调用栈上\n return false; // 没有找到环路，返回 false\n}\n\nint main() {\n int N, M; // 端点数和线路数\n while (cin >> N >> M && (N != 0 || M != 0)) { // 输入循环\n vector<vector<int>> graph(N + 1); // 创建图的邻接表\n for (int i = 0; i < M; ++i) { // 输入线路信息\n int A, B; // 线路的两端节点\n cin >> A >> B; // 输入线路的两端节点\n graph[A].push_back(B); // 将节点 B 加入节点 A 的邻居列表中\n graph[B].push_back(A); // 将节点 A 加入节点 B 的邻居列表中\n }\n if (isConnected(graph, N) && !hasCycle(graph, N)) { // 判断系统是否符合要求\n cout << "Yes" << endl; // 输出 Yes\n } else {\n cout << "No" << endl; // 输出 No\n }\n cout << endl; // 输出空行\n }\n return 0; // 返回 0\n}\n\n