(C卷,200分)- 查找一个有向网络的头节点和尾节点（Java & JS & Python & C）

题目描述

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

每个节点用正整数表示。

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

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

输入描述

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

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

输出描述

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

备注

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

用例

题目解析

用例1图示

用例2图示

本题可以通过拓扑排序解题。

关于拓扑排序的知识，大家如果不知道的话，可以先看下：

了解拓扑排序后，我们就可以按照拓扑排序的思路不停剥离图中入度为0的点，每当剥离一个入度为0的点A，我们都需要做如下判断：

• A点如果没有后继点，则说明A点的出度为0，因此A点为尾节点
• A点如果有后继点，则A点的所有后继点的入度-1，如果后继点中-1后出现新的入度为0的节点，则加入度0点的队列，等待下次剥离

在上面过程中，我们需要统计被剥离点的个数，使用count表示，如果图中节点总数为total，那么当拓扑排序完成后，count < total 的话，则说明图中存在环。

本题的输出描述要求多个尾节点降序输出

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

而题目用例2输出的尾节点是升序输出的

0 1 2

这里互相矛盾，这里以用例输出为准来，即如果有多个尾节点，则升序输出。实际考试注意下。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const n = parseInt(await readline());
  const tmp = (await readline()).split(" ").map(Number);

  // 记录每个点的入度
  const inDegree = {};
  // 记录每个点的后继点集合
  const next = {};

  // 记录图中点
  const set = new Set();

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

    // 收集图中所有节点
    set.add(a);
    set.add(b);

    // b点入度+1, 下面 ?? 是新特性语法，牛客平台可能不支持，a ?? b 的结果是：如果a是null或undefined，则返回b，否则返回a
    inDegree[b] = (inDegree[b] ?? 0) + 1;

    // a点的后继点集合纳入b
    if (next[a]) {
      next[a].push(b);
    } else {
      next[a] = [b];
    }
  }

  // 图中总共total个节点
  const total = set.size;

  // head记录图的头节点
  let head = 0;
  // 队列记录入度为0的点
  const queue = [];

  for (let p of set) {
    // 题目描述中说图中只有一个首节点，首节点是入度为0的节点，因此如果某节点p没有入度，则为头节点
    if (inDegree[p] == undefined) {
      head = p;
      queue.push(p);
      break;
    }
  }

  // tails记录所有尾节点
  const tails = [];
  // count记录已被剥去的点个数，如果图中存在环，则必然最终count < total
  let count = 0;

  while (queue.length > 0) {
    // 剥离入度为0的点
    const fa = queue.shift();
    count++;

    // 如果fa没有后继点，即fa没有出度，则fa是尾节点
    if (next[fa] == undefined) {
      tails.push(fa);
      continue;
    }

    // 如果fa有后继点，则其所有后继点入度-1
    for (let ch of next[fa]) {
      inDegree[ch] -= 1;

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

  if (count != total) {
    // 如果存在环，则必然count < total
    console.log(-1);
  } else {
    // 如果不存在环，则打印头节点和尾节点
    // 注意本题描述存在冲突（用例2输出的尾节点是从小到大排序的，而题目输出描述是要求尾节点从大到小排序），这里以用例为准
    console.log(head, tails.sort((a, b) => a - b).join(" "));
  }
})();

Java算法源码

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    // 记录每个点的入度
    HashMap<Integer, Integer> inDegree = new HashMap<>();
    // 记录每个点的后继点集合
    HashMap<Integer, ArrayList<Integer>> next = new HashMap<>();

    // 记录图中点
    HashSet<Integer> set = new HashSet<>();

    for (int i = 0; i < n; i++) {
      // 从 a 到 b 的路径
      int a = sc.nextInt();
      int b = sc.nextInt();

      // 收集图中所有节点
      set.add(a);
      set.add(b);

      // b点入度+1
      inDegree.put(b, inDegree.getOrDefault(b, 0) + 1);

      // a点的后继点集合纳入b
      next.putIfAbsent(a, new ArrayList<>());
      next.get(a).add(b);
    }

    // 图中总共total个节点
    int total = set.size();

    // head记录图的头节点
    int head = 0;

    // 队列记录入度为0的点
    LinkedList<Integer> queue = new LinkedList<>();
    for (int p : set) {
      // 题目描述中说图中只有一个首节点，首节点是入度为0的节点，因此如果某节点p没有入度，则为头节点
      if (!inDegree.containsKey(p)) {
        head = p;
        queue.add(p);
        break;
      }
    }

    // tails记录所有尾节点
    ArrayList<Integer> tails = new ArrayList<>();

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

    while (queue.size() > 0) {
      // 剥离入度为0的点
      int fa = queue.removeFirst();
      count++;

      // 如果fa没有后继点，即fa没有出度，则fa是尾节点
      if (!next.containsKey(fa)) {
        tails.add(fa);
        continue;
      }

      // 如果fa有后继点，则其所有后继点入度-1
      for (int ch : next.get(fa)) {
        inDegree.put(ch, inDegree.get(ch) - 1);

        // 如果ch点入度变为0，则加入队列
        if (inDegree.get(ch) == 0) {
          queue.add(ch);
        }
      }
    }

    if (count != total) {
      // 如果存在环，则必然count < total
      System.out.println(-1);
    } else {
      // 如果不存在环，则打印头节点和尾节点
      StringJoiner sj = new StringJoiner(" ");

      sj.add(head + "");
      // 注意本题描述存在冲突（用例2输出的尾节点是从小到大排序的，而题目输出描述是要求尾节点从大到小排序），这里以用例为准
      tails.stream().sorted((a, b) -> a - b).forEach(p -> sj.add(p + ""));

      System.out.println(sj);
    }
  }
}

Python算法源码

# 输入获取
n = int(input())
tmp = list(map(int, input().split()))


# 算法入口
def getResult():
    # 记录每个点的入度
    inDegree = {}
    # 记录每个点的后继点集合
    nxt = {}

    # 记录图中点
    points = set()

    for i in range(0, 2 * n, 2):
        # 从 a 到 b 的路径
        a = tmp[i]
        b = tmp[i + 1]

        # 收集图中所有节点
        points.add(a)
        points.add(b)

        # b点入度+1
        inDegree.setdefault(b, 0)
        inDegree[b] += 1

        # a点的后继点集合纳入b
        nxt.setdefault(a, [])
        nxt[a].append(b)

    # 图中总共total个节点
    total = len(points)

    # head记录图的头节点
    head = 0
    # 队列记录入度为0的点
    queue = []

    for p in points:
        # 题目描述中说图中只有一个首节点，首节点是入度为0的节点，因此如果某节点p没有入度，则为头节点
        if p not in inDegree:
            head = p
            queue.append(p)
            break

    # tails记录所有尾节点
    tails = []

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

    while len(queue) > 0:
        # 剥离入度为0的点
        fa = queue.pop(0)
        count += 1

        # 如果fa没有后继点，即fa没有出度，则fa是尾节点
        if fa not in nxt:
            tails.append(fa)
            continue

        # 如果fa有后继点，则其所有后继点入度-1
        for ch in nxt[fa]:
            inDegree[ch] -= 1

            # 如果ch点入度变为0，则加入队列
            if inDegree[ch] == 0:
                queue.append(ch)

    if count != total:
        # 如果存在环，则必然count < total
        print(-1)
    else:
        # 如果不存在环，则打印头节点和尾节点
        # 注意本题描述存在冲突（用例2输出的尾节点是从小到大排序的，而题目输出描述是要求尾节点从大到小排序），这里以用例为准
        tails.sort()
        print(head, " ".join(map(str, tails)))


# 算法调用
getResult()

C算法源码

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

#define MAX_SIZE 10000

/** 基于链表实现队列 **/
typedef struct ListNode {
    int ele;
    struct ListNode *next;
} ListNode;

typedef struct LinkedList {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
    link->size = 0;
    link->head = NULL;
    link->tail = NULL;
    return link;
}

void addLast_LinkedList(LinkedList *link, int ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));
    node->ele = ele;
    node->next = NULL;

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        link->tail = node;
    }

    link->size++;
}

int removeFirst_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->head;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
    }

    link->size--;

    return removed->ele;
}

int cmp(const void *a, const void *b) {
    return *((int *) a) - *((int *) b);
}

int main() {
    int n;
    scanf("%d", &n);

    // 记录每个点的入度
    int inDegree[MAX_SIZE] = {0};
    // 记录每个点的后继点集合
    LinkedList *next[MAX_SIZE] = {NULL};

    // 记录图中点
    LinkedList *points = new_LinkedList();
    int occurs[MAX_SIZE] = {0};

    for (int i = 0; i < n; i++) {
        // 从 a 到 b 的路径
        int a, b;
        scanf("%d %d", &a, &b);

        // 收集图中所有节点
        if (!occurs[a]) {
            addLast_LinkedList(points, a);
            occurs[a] = 1;
        }

        if (!occurs[b]) {
            addLast_LinkedList(points, b);
            occurs[b] = 1;
        }

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

        if (next[a] == NULL) {
            next[a] = new_LinkedList();
        }
        // a点的后继点集合纳入b
        addLast_LinkedList(next[a], b);
    }

    // 图中总共total个节点
    int total = points->size;
    // head记录图的头节点
    int head = 0;

    // 队列记录入度为0的点
    LinkedList *queue = new_LinkedList();

    ListNode *cur = points->head;
    while (cur != NULL) {
        int p = cur->ele;

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

        cur = cur->next;
    }

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

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

    while (queue->size > 0) {
        // 剥离入度为0的点
        int fa = removeFirst_LinkedList(queue);
        count++;

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

        // 如果fa有后继点，则其所有后继点入度-1
        ListNode *cur = next[fa]->head;
        while (cur != NULL) {
            int ch = cur->ele;

            inDegree[ch] -= 1;

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

            cur = cur->next;
        }
    }


    if (count != total) {
        // 如果存在环，则必然count < total
        printf("-1");
    } else {
        // 如果不存在环，则打印头节点和尾节点
        printf("%d ", head);

        // 注意本题描述存在冲突（用例2输出的尾节点是从小到大排序的，而题目输出描述是要求尾节点从大到小排序），这里以用例为准
        qsort(tails, tails_size, sizeof(int), cmp);

        for (int i = 0; i < tails_size; i++) {
            printf("%d", tails[i]);

            if (i < tails_size - 1) {
                printf(" ");
            }
        }
    }


    return 0;
}