返回目录

题目描述

给定一个有向图，图中可能包含有环，图使用二维矩阵表示，每一行的第一列表示起始节点，第二列表示终止节点，如 [0, 1] 表示从 0 到 1 的路径。

每个节点用正整数表示。求这个数据的首节点与尾节点，题目给的用例会是一个首节点，但可能存在多个尾节点。同时图中可能含有环。如果图中含有环，返回 [-1]。

说明：入度为0是首节点，出度为0是尾节点。

image.png

输入描述

第一行为后续输入的键值对数量N（N ≥ 0）

第二行为2N个数字。每两个为一个起点，一个终点.

输出描述

输出一行头节点和尾节点。如果有多个尾节点，按从小到大的顺序输出

备注
  • 如果图有环，输出为 -1
  • 所有输入均合法，不会出现不配对的数据

示例：

输入4
0 1 0 2 1 2 2 3
输出0 3
说明image.png

解题思路

环的检测

  1. DFS实现:

    • 为了进行DFS，首先构建了图的邻接表表示。这是通过将边信息转换成每个节点的邻接节点列表来完成的。
    • 然后，对每个节点进行DFS遍历。

    • 在遍历过程中，维护两个集合：visited和 recStack。

      • visited用于记录已经访问过的节点。
      • recStack用于记录当前递归调用栈中的节点。

  2. 检测环的逻辑:

    • 在DFS遍历中，如果当前节点已在 recStack中，则表示找到了一个环，因为这意味着在遍历过程中回到了正在访问的节点。
    • 如果节点在 visited中但不在 recStack中，这意味着节点已被访问且没有形成环。
    • 对每个邻接节点重复这个过程。

  3. 结束条件:

    • 如果在任何节点的DFS遍历中检测到环，立即返回 true，表示图中存在环。
    • 如果所有节点都被遍历过，且没有检测到环，则返回 false。

确定起点和终点

  1. 起点和终点的定义:

    • 起点是指没有入度的节点，即没有其他节点指向它的节点。
    • 终点是指没有出度的节点，即它不指向任何其他节点的节点。

  2. 查找方法:

    • 遍历所有节点，检查它们的入度和出度。
    • 对于每个节点，如果它在 inDegree映射中没有记录，那么它就是起点。
    • 如果它在 outDegree映射中没有记录，那么它就是终点。

  3. 存储结果:

    • 结果数组首先存储起点，然后是所有终点。
    • 这个数组最后返回作为方法的输出。

Python算法源码

def detect_cycle(graph, node, visited, rec_stack):
    # 如果节点在递归栈中，表示存在环
    if node in rec_stack:
        return True
    # 如果节点已经被访问过，说明该路径无环
    if node in visited:
        return False

    visited.add(node)
    rec_stack.add(node)

    # 遍历节点的邻居
    for neighbor in graph.get(node, []):
        if detect_cycle(graph, neighbor, visited, rec_stack):
            return True

    rec_stack.remove(node)
    return False

def has_cycle(nodes, edges):
    # 构建图的邻接表
    graph = {}
    for node in nodes:
        graph[node] = []

    for i in range(0, len(edges), 2):
        graph[edges[i]].append(edges[i + 1])

    visited = set()
    rec_stack = set()

    # 检测图中是否存在环
    for node in nodes:
        if detect_cycle(graph, node, visited, rec_stack):
            return True

    return False

def find_start_and_end_nodes(edges):
    in_degree = {}  # 入度映射
    out_degree = {}  # 出度映射
    nodes = set()  # 节点集合

    # 构建入度和出度映射
    for i in range(0, len(edges), 2):
        start, end = edges[i], edges[i + 1]
        nodes.add(start)
        nodes.add(end)
        in_degree[end] = in_degree.get(end, 0) + 1
        out_degree[start] = out_degree.get(start, 0) + 1

    # 如果图中存在环，返回-1
    if has_cycle(nodes, edges):
        return [-1]

    end_nodes = []  # 终点节点列表
    start_node = -1  # 起点节点

    # 寻找起点和终点
    for node in nodes:
        if node not in in_degree:
            start_node = node
        if node not in out_degree:
            end_nodes.append(node)

    return [start_node] + end_nodes

def main():
    input()  # 读取并丢弃第一行
    edges = list(map(int, input().split()))

    result = find_start_and_end_nodes(edges)
    print(*result)

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100005

// 定义图节点结构体
struct Node {
    int value;
    struct Node* next;
};

// 定义队列结构体
struct Queue {
    int front, rear;
    int capacity;
    int* array;
};

// 创建新节点
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

// 创建队列
struct Queue* createQueue(int capacity) {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->rear = -1;
    queue->array = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
}

// 判断队列是否为空
int isEmpty(struct Queue* queue) {
    return queue->front == -1;
}

// 入队
void enqueue(struct Queue* queue, int value) {
    queue->array[++queue->rear] = value;
    if (queue->front == -1)
        ++queue->front;
}

// 出队
int dequeue(struct Queue* queue) {
    int value = queue->array[queue->front++];
    if (queue->front > queue->rear)
        queue->front = queue->rear = -1;
    return value;
}

// 算法入口函数
void getResult(int n, int tmp[]) {
    // 记录每个点的入度
    int inDegree[MAX_SIZE] = {0};
    // 记录每个点的后继点集合
    struct Node* nxt[MAX_SIZE] = {NULL};
    // 记录图中点
    int points[MAX_SIZE] = {0};

    for (int i = 0; i < 2 * n; i += 2) {
        // 从 a 到 b 的路径
        int a = tmp[i];
        int b = tmp[i + 1];

        // 收集图中所有节点
        points[a] = points[b] = 1;

        // b点入度+1
        inDegree[b]++;

        // a点的后继点集合纳入b
        struct Node* newNode = createNode(b);
        if (nxt[a] == NULL)
            nxt[a] = newNode;
        else {
            newNode->next = nxt[a];
            nxt[a] = newNode;
        }
    }

    // 图中总共total个节点
    int total = 0;
    for (int i = 0; i < MAX_SIZE; ++i) {
        if (points[i] == 1)
            total++;
    }

    // head记录图的头节点
    int head = 0;
    // 队列记录入度为0的点
    struct Queue* queue = createQueue(MAX_SIZE);

    for (int i = 0; i < MAX_SIZE; ++i) {
        // 题目描述中说图中只有一个首节点，首节点是入度为0的节点，因此如果某节点p没有入度，则为头节点
        if (points[i] == 1 && inDegree[i] == 0) {
            head = i;
            enqueue(queue, i);
            break;
        }
    }

    // tails记录所有尾节点
    int tails[MAX_SIZE], tailIndex = 0;

    // count记录已被剥去的点个数，如果图中存在环，则必然最终count < total
    int count = 0;

    while (!isEmpty(queue)) {
        // 剥离入度为0的点
        int fa = dequeue(queue);
        count++;

        // 如果fa没有后继点，即fa没有出度，则fa是尾节点
        if (nxt[fa] == NULL) {
            tails[tailIndex++] = fa;
            continue;
        }

        // 如果fa有后继点，则其所有后继点入度-1
        struct Node* current = nxt[fa];
        while (current != NULL) {
            int ch = current->value;
            inDegree[ch]--;

            // 如果ch点入度变为0，则加入队列
            if (inDegree[ch] == 0)
                enqueue(queue, ch);

            current = current->next;
        }
    }

    if (count != total) {
        // 如果存在环，则必然count < total
        printf("-1\n");
    } else {
        // 如果不存在环，则打印头节点和尾节点
        // 注意本题描述存在冲突（用例2输出的尾节点是从小到大排序的，而题目输出描述是要求尾节点从大到小排序），这里以用例为准
        printf("%d", head);
        for (int i = tailIndex - 1; i >= 0; --i)
            printf(" %d", tails[i]);
        printf("\n");
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int tmp[2 * MAX_SIZE];
    for (int i = 0; i < 2 * n; ++i)
        scanf("%d", &tmp[i]);

    getResult(n, tmp);

    return 0;
}

Java算法源码

import java.util.*;

public class Main {
    // 递归检测图中是否有环
    public static boolean detectCycle(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited, Set<Integer> recStack) {
        if (recStack.contains(node)) {
            return true;
        }
        if (visited.contains(node)) {
            return false;
        }

        visited.add(node);
        recStack.add(node);

        List<Integer> neighbors = graph.get(node);
        if (neighbors != null) {
            for (int neighbor : neighbors) {
                if (detectCycle(graph, neighbor, visited, recStack)) {
                    return true;
                }
            }
        }

        recStack.remove(node);
        return false;
    }

    // 检测图中是否有环
    public static boolean hasCycle(Set<Integer> nodes, List<Integer> edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int node : nodes) {
            graph.put(node, new ArrayList<>());
        }

        for (int i = 0; i < edges.size(); i += 2) {
            int start = edges.get(i);
            int end = edges.get(i + 1);
            graph.get(start).add(end);
        }

        Set<Integer> visited = new HashSet<>();
        Set<Integer> recStack = new HashSet<>();

        for (int node : nodes) {
            if (detectCycle(graph, node, visited, recStack)) {
                return true;
            }
        }

        return false;
    }

    // 寻找起点和终点节点
    public static List<Integer> findStartAndEndNodes(List<Integer> edges) {
        Map<Integer, Integer> inDegree = new HashMap<>();
        Map<Integer, Integer> outDegree = new HashMap<>();
        Set<Integer> nodes = new HashSet<>();

        // 构建入度和出度的映射
        for (int i = 0; i < edges.size(); i += 2) {
            int start = edges.get(i);
            int end = edges.get(i + 1);
            nodes.add(start);
            nodes.add(end);
            inDegree.put(end, inDegree.getOrDefault(end, 0) + 1);
            outDegree.put(start, outDegree.getOrDefault(start, 0) + 1);
        }

        // 检测是否有环
        if (hasCycle(nodes, edges)) {
            return Collections.singletonList(-1);
        }

        // 寻找起点和终点
        List<Integer> endNodes = new ArrayList<>();
        int startNode = -1;
        for (int node : nodes) {
            if (!inDegree.containsKey(node)) {
                startNode = node;
            }
            if (!outDegree.containsKey(node)) {
                endNodes.add(node);
            }
        }

        List<Integer> result = new ArrayList<>();
        result.add(startNode);
        result.addAll(endNodes);
        return result;
    }

    // 主函数
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        scanner.nextLine(); // 读取N，但在这个程序中不使用
        String line = scanner.nextLine(); // 读取边的数据

        String[] edgeTokens = line.split(" ");
        List<Integer> edges = new ArrayList<>();
        for (String token : edgeTokens) {
            edges.add(Integer.parseInt(token));
        }

        List<Integer> result = findStartAndEndNodes(edges);
        for (int num : result) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}
最后修改：2024 年 04 月 08 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏