题面描述

给定一个有向图，该图可能包含环，使用二维矩阵表示每条边。每行的第一列是起始节点，第二列是终止节点。我们需要找到图中的首节点和尾节点。首节点是入度为0的节点，尾节点是出度为0的节点。如果图中有环，则返回 [-1]。

思路

拓扑排序板子题，注意统计排序后的总节点如果不等于原来节点个数说明有环

具体步骤

1. 图的表示：使用邻接表或入度、出度计数器来表示图的结构。
2. 入度和出度计算：遍历所有边，计算每个节点的入度和出度。
3. 检测环：使用拓扑排序来检测环。如果在拓扑排序过程中无法访问所有节点，则说明图中有环。
4. 寻找首节点和尾节点：遍历所有节点，找到入度为0的节点（首节点）和出度为0的节点（尾节点）。
5. 输出结果：根据条件输出首节点和尾节点。

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