#P3206. 查找一个有向网络的头节点和尾节点(200分)
-
1000ms
Tried: 77
Accepted: 23
Difficulty: 3
所属公司 :
华为od
查找一个有向网络的头节点和尾节点(200分)
题面描述
给定一个有向图,该图可能包含环,使用二维矩阵表示每条边。每行的第一列是起始节点,第二列是终止节点。我们需要找到图中的首节点和尾节点。首节点是入度为0的节点,尾节点是出度为0的节点。如果图中有环,则返回 [-1]。
思路
拓扑排序板子题,注意统计排序后的总节点如果不等于原来节点个数说明有环
具体步骤
- 图的表示:使用邻接表或入度、出度计数器来表示图的结构。
- 入度和出度计算:遍历所有边,计算每个节点的入度和出度。
- 检测环:使用拓扑排序来检测环。如果在拓扑排序过程中无法访问所有节点,则说明图中有环。
- 寻找首节点和尾节点:遍历所有节点,找到入度为0的节点(首节点)和出度为0的节点(尾节点)。
- 输出结果:根据条件输出首节点和尾节点。
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int edgeCount;
cin >> edgeCount;
if (edgeCount == 0) {
cout << -1 << endl;
return 0;
}
// 记录每个点的入度
map<int, int> inDegree;
// 记录每个点的后继点集合
map<int, vector<int>> adjacencyList;
// 记录图中节点
set<int> allNodes;
for (int i = 0; i < edgeCount; i++) {
// 从 a 到 b 的路径
int from, to;
cin >> from >> to;
// 收集图中所有节点
allNodes.insert(from);
allNodes.insert(to);
// b点入度+1
inDegree[to]++;
// a点的后继点集合纳入b
if (adjacencyList.count(from) == 0) {
adjacencyList[from] = vector<int>();
}
adjacencyList[from].emplace_back(to);
}
// 图中总共节点数量
int totalNodes = allNodes.size();
// 记录图的首节点
int startNode = 0;
// 队列记录入度为0的点
deque<int> zeroIndegreeQueue;
for (const auto &node : allNodes) {
// 找到入度为0的节点作为首节点
if (inDegree.count(node) == 0) {
startNode = node;
zeroIndegreeQueue.emplace_back(node);
break;
}
}
// tails记录所有尾节点
vector<int> endNodes;
// 记录已剥离的节点数量
int processedCount = 0;
while (!zeroIndegreeQueue.empty()) {
// 剥离入度为0的点
int currentNode = zeroIndegreeQueue.front();
zeroIndegreeQueue.pop_front();
processedCount++;
// 如果currentNode没有后继点,则currentNode是尾节点
if (adjacencyList.count(currentNode) == 0) {
endNodes.emplace_back(currentNode);
continue;
}
// 如果currentNode有后继点,则其所有后继点入度-1
for (const auto &successor : adjacencyList[currentNode]) {
inDegree[successor]--;
// 如果后继点的入度变为0,则加入队列
if (inDegree[successor] == 0) {
zeroIndegreeQueue.emplace_back(successor);
}
}
}
if (processedCount != totalNodes) {
// 如果存在环,则必然processedCount < totalNodes
cout << -1 << endl;
} else {
// 如果不存在环,则打印首节点和尾节点
cout << startNode << " ";
// 将尾节点按从小到大排序
sort(endNodes.begin(), endNodes.end());
for (const auto &item : endNodes) {
cout << item << " ";
}
cout << endl;
}
return 0;
}
python
from collections import defaultdict, deque
def main():
edge_count = int(input())
if edge_count == 0:
print(-1)
return
# 记录每个点的入度
in_degree = defaultdict(int)
# 记录每个点的后继点集合
adjacency_list = defaultdict(list)
# 记录图中节点
all_nodes = set()
# 读取一行所有边的信息
edges = list(map(int, input().split()))
# 每两个元素构成一条边
for i in range(0, len(edges), 2):
from_node = edges[i]
to_node = edges[i + 1]
# 收集图中所有节点
all_nodes.add(from_node)
all_nodes.add(to_node)
# b点入度+1
in_degree[to_node] += 1
# a点的后继点集合纳入b
adjacency_list[from_node].append(to_node)
# 图中总共节点数量
total_nodes = len(all_nodes)
# 记录图的首节点
start_node = None
# 队列记录入度为0的点
zero_indegree_queue = deque()
for node in all_nodes:
# 找到入度为0的节点作为首节点
if in_degree[node] == 0:
start_node = node
zero_indegree_queue.append(node)
break
# tails记录所有尾节点
end_nodes = []
# 记录已剥离的节点数量
processed_count = 0
while zero_indegree_queue:
# 剥离入度为0的点
current_node = zero_indegree_queue.popleft()
processed_count += 1
# 如果current_node没有后继点,则current_node是尾节点
if current_node not in adjacency_list:
end_nodes.append(current_node)
continue
# 如果current_node有后继点,则其所有后继点入度-1
for successor in adjacency_list[current_node]:
in_degree[successor] -= 1
# 如果后继点的入度变为0,则加入队列
if in_degree[successor] == 0:
zero_indegree_queue.append(successor)
if processed_count != total_nodes:
# 如果存在环,则必然processed_count < total_nodes
print(-1)
else:
# 如果不存在环,则打印首节点和尾节点
print(start_node, end=" ")
# 将尾节点按从小到大排序
end_nodes.sort()
print(" ".join(map(str, end_nodes)))
if __name__ == "__main__":
main()
java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int edgeCount = scanner.nextInt();
if (edgeCount == 0) {
System.out.println(-1);
return;
}
// 记录每个点的入度
Map<Integer, Integer> inDegree = new HashMap<>();
// 记录每个点的后继点集合
Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
// 记录图中节点
Set<Integer> allNodes = new HashSet<>();
// 读取所有边的信息
for (int i = 0; i < edgeCount; i++) {
int fromNode = scanner.nextInt();
int toNode = scanner.nextInt();
// 收集图中所有节点
allNodes.add(fromNode);
allNodes.add(toNode);
// b点入度+1
inDegree.put(toNode, inDegree.getOrDefault(toNode, 0) + 1);
// a点的后继点集合纳入b
adjacencyList.putIfAbsent(fromNode, new ArrayList<>());
adjacencyList.get(fromNode).add(toNode);
}
// 图中总共节点数量
int totalNodes = allNodes.size();
// 记录图的首节点
Integer startNode = null;
// 队列记录入度为0的点
Deque<Integer> zeroIndegreeQueue = new ArrayDeque<>();
for (int node : allNodes) {
// 找到入度为0的节点作为首节点
if (!inDegree.containsKey(node)) {
startNode = node;
zeroIndegreeQueue.add(node);
break;
}
}
// tails记录所有尾节点
List<Integer> endNodes = new ArrayList<>();
// 记录已剥离的节点数量
int processedCount = 0;
while (!zeroIndegreeQueue.isEmpty()) {
// 剥离入度为0的点
int currentNode = zeroIndegreeQueue.poll();
processedCount++;
// 如果currentNode没有后继点,则currentNode是尾节点
if (!adjacencyList.containsKey(currentNode)) {
endNodes.add(currentNode);
continue;
}
// 如果currentNode有后继点,则其所有后继点入度-1
for (int successor : adjacencyList.get(currentNode)) {
inDegree.put(successor, inDegree.get(successor) - 1);
// 如果后继点的入度变为0,则加入队列
if (inDegree.get(successor) == 0) {
zeroIndegreeQueue.add(successor);
}
}
}
if (processedCount != totalNodes) {
// 如果存在环,则必然processedCount < totalNodes
System.out.println(-1);
} else {
// 如果不存在环,则打印首节点和尾节点
System.out.print(startNode + " ");
// 将尾节点按从小到大排序
Collections.sort(endNodes);
for (int item : endNodes) {
System.out.print(item + " ");
}
System.out.println();
}
scanner.close();
}
}
题目内容
给定一个有向图,图中可能包含有环,图使用二维矩阵表示,每一行的第一列表示起始节点,第二列表示终止节点,如 [0,1] 表示从 0 到 1 的路径。
每个节点用正整数表示。
求这个数据的首节点与尾节点,题目给的用例会是一个首节点,但可能存在多个尾节点。同时图中可能含有环。如果图中含有环,返回 [−1]。
说明:入度为 0 是首节点,出度为 0 是尾节点。

输入描述
第一行为后续输入的键值对数量 N(N≥0)
第二行为 2N 个数字。每两个为一个起点,一个终点,如:
输出描述
输出一行头节点和尾节点。如果有多个尾节点,按从小到大的顺序输出。
备注
- 如果图有环,输出为 −1
- 所有输入均合法,不会出现不配对的数据
样例1
输入
4
0 1 0 2 1 2 2 3
输出
0 3
样例2
输入
2
0 1 0 2
输出
0 1 2