【BFS】2024D-查找一个有向网络的头节点和尾节点

题目描述与示例

题目描述

给定一个有向图，图中可能包含有环，有向边用两个节点表示。第一个整数表示起始节点，第二个整数表示终止节点，如0 1表示存在从0到1的路径。每个节点用正整数表示，求这个数据的头节点与尾节点，题目给的用例会是一个头节点，但可能存在多个尾节点。同时，图中可能含有环，如果图中含有环，返回-1。

img

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

输入描述

第一行为后续输入的键值对数量N >= 0，第二行为2N个数字。每两个为一个起点，一个终点。

输出描述

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

备注

如果图有环，输出为-1

所有输入均合法，不会出现不配对的数据

示例

输入

4
1 2 1 3 2 4 3 4

输出

1 4

说明

该例子表示以下有向图。头节点为1，尾节点为4

img

解题思路

本题就是拓扑排序模板题。

假设输入确认没有环，那么题目的提示已经告诉了我们应该如何找到头节点和尾节点。

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

由于进行拓扑排序之前需要同时构建邻接表和入度****哈希表，即

neighbor_dic = defaultdict(list)
indegree_dic = defaultdict(int)

for i in range(0, 2*n, 2):
    a, b = lst[i], lst[i+1]
    indegree_dic[b] += 1
    neighbor_dic[a].append(b)

则无需再额外构建出度数组。邻接表可以起到出度数组的作用。

头节点的判断

如果某一个节点k位于邻接表的key中（说明存在以k为起始节点的边），但其入度为0（说明不存在以k为终止节点的边），则说明k是一个头节点。即

head_node = -1
for k in neighbor_dic.keys():
    if k not in indegree_dic:
        head_node = k
        break

尾节点的判断

如果某一个节点k入度不为0（说明存在以k为终止节点的边），但其不位于邻接表的key中（说明不存在以k为起始节点的边），则说明k是一个尾节点。即

tail_nodes = list()
for k in indegree_dic.keys():
    if k not in neighbor_dic:
        tail_nodes.append(k)

环的判断

头节点和尾节点非常容易直接通过邻接表和入度哈希表计算得到。

但本题的核心在于判断该有向图是否存在环。

使用拓扑排序来进行环的判断。如果

• 该有向图可以完成拓扑排序，则说明不存在环，输出相应的头节点和尾节点。
• 该有向图不能完成拓扑排序，则说明存在环，输出-1。

其中，能够成功完成拓扑排序的标准是：拓扑排序结束之后，所有节点的入度均降为0。

故设计函数check()来检查所给定的有向图是否能够成功完成拓扑排序

def check(head_node, neighbor_dic, indegree_dic):
    q = deque()
    q.append(head_node)
    while q:
        cur_node = q.popleft()
        for nxt_node in neighbor_dic[cur_node]:
            indegree_dic[nxt_node] -= 1
            if indegree_dic[nxt_node] == 0:
                q.append(nxt_node)
    return all(v == 0 for v in indegree_dic.values())

代码

Python

# 题目：【BFS】2023C-查找一个有向网络的头节点和尾节点
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：BFS/拓扑排序
# 代码看不懂的地方，请直接在群上提问


from collections import deque, defaultdict


# 检查给定数据能够完成拓扑排序（是否存在环）的函数
def check(head_node, neighbor_dic, indegree_dic):
    # 构建队列
    q = deque()
    q.append(head_node)
    # 进行BFS
    while q:
        # 弹出当前队头节点cur_node
        cur_node = q.popleft()
        # 考虑cur_node的所有近邻节点nxt_node
        for nxt_node in neighbor_dic[cur_node]:
            # 近邻节点的入度-1
            indegree_dic[nxt_node] -= 1
            # 如果近邻节点的入度降为0，将其加入队列中
            if indegree_dic[nxt_node] == 0:
                q.append(nxt_node)

    # 如果最终所有节点的入度均为0，即indegree_dic.values()均为0
    # 则说明成功完成拓扑排序，有向图中不存在环
    return all(v == 0 for v in indegree_dic.values())


# 输入边数n
n = int(input())
# 输入2n个数据，每2个节点一组，一共有n组数据
lst = list(map(int, input().split()))

# 构建邻接表
neighbor_dic = defaultdict(list)

# 构建入度哈希表（因为节点的个数不确定，因此用哈希表而不是数组）
indegree_dic = defaultdict(int)

# 每两个一组，取lst中的数据
for i in range(0, 2*n, 2):
    # a为该条边的起始节点，b为该条边的终止节点
    # 即存在a指向b
    a, b = lst[i], lst[i+1]
    # 节点b的入度+1
    indegree_dic[b] += 1
    # 节点a的邻接表延长
    neighbor_dic[a].append(b)

head_node = -1
# 遍历邻接表中的所有起始节点k
# 如果k不存在于入度哈希表中
# 说明k的入度为0，即k是头节点
for k in neighbor_dic.keys():
    if k not in indegree_dic:
        # 由于题目明确只存在一个头节点
        # 因此可以直接退出循环
        head_node = k
        break

# 构建尾节点序列
tail_nodes = list()
# 遍历入度哈希表中的所有节点k
# 如果k不存在于邻接表中
# 说明k不是任何一条边的起始节点，即k是一个尾节点
for k in indegree_dic.keys():
    if k not in neighbor_dic:
        tail_nodes.append(k)

# 尾节点数组进行排序
tail_nodes.sort()

# 调用check()函数，进行拓扑排序
# 如果能够顺利完成拓扑排序，则说明图中不存在环，直接输出头节点和若干尾节点
# 否则输出-1
print(head_node, *tail_nodes) if check(head_node, neighbor_dic, indegree_dic) else print(-1)

Java

import java.util.*;

public class Main {
    public static boolean check(int headNode, Map<Integer, List<Integer>> neighborDic, Map<Integer, Integer> indegreeDic) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(headNode);
        
        while (!q.isEmpty()) {
            int curNode = q.poll();
            
            for (int nxtNode : neighborDic.getOrDefault(curNode, new ArrayList<>())) {
                indegreeDic.put(nxtNode, indegreeDic.get(nxtNode) - 1);
                if (indegreeDic.get(nxtNode) == 0) {
                    q.offer(nxtNode);
                }
            }
        }
        
        for (int value : indegreeDic.values()) {
            if (value > 0) {
                return false;
            }
        }
        
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] lst = new int[2 * n];
        for (int i = 0; i < 2 * n; i++) {
            lst[i] = scanner.nextInt();
        }
        
        Map<Integer, List<Integer>> neighborDic = new HashMap<>();
        Map<Integer, Integer> indegreeDic = new HashMap<>();
        
        for (int i = 0; i < 2 * n; i += 2) {
            int a = lst[i], b = lst[i + 1];
            indegreeDic.put(b, indegreeDic.getOrDefault(b, 0) + 1);
            neighborDic.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
        }
        
        int headNode = -1;
        for (int node : neighborDic.keySet()) {
            if (!indegreeDic.containsKey(node)) {
                headNode = node;
                break;
            }
        }
        
        List<Integer> tailNodes = new ArrayList<>();
        for (int node : indegreeDic.keySet()) {
            if (!neighborDic.containsKey(node)) {
                tailNodes.add(node);
            }
        }
        Collections.sort(tailNodes);
        
        if (check(headNode, neighborDic, indegreeDic)) {
            System.out.print(headNode + " ");
            for (int node : tailNodes) {
                System.out.print(node + " ");
            }
            System.out.println();
        } else {
            System.out.println(-1);
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
using namespace std;

bool check(int headNode, unordered_map<int, vector<int>>& neighborDic, unordered_map<int, int>& indegreeDic) {
    queue<int> q;
    q.push(headNode);
    
    while (!q.empty()) {
        int curNode = q.front();
        q.pop();
        
        for (int nxtNode : neighborDic[curNode]) {
            indegreeDic[nxtNode]--;
            if (indegreeDic[nxtNode] == 0) {
                q.push(nxtNode);
            }
        }
    }
    
    for (auto entry : indegreeDic) {
        if (entry.second > 0) {
            return false;
        }
    }
    
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> lst(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        cin >> lst[i];
    }
    
    unordered_map<int, vector<int>> neighborDic;
    unordered_map<int, int> indegreeDic;
    
    for (int i = 0; i < 2 * n; i += 2) {
        int a = lst[i], b = lst[i + 1];
        indegreeDic[b]++;
        neighborDic[a].push_back(b);
    }
    
    int headNode = -1;
    for (auto entry : neighborDic) {
        if (indegreeDic.find(entry.first) == indegreeDic.end()) {
            headNode = entry.first;
            break;
        }
    }
    
    vector<int> tailNodes;
    for (auto entry : indegreeDic) {
        if (neighborDic.find(entry.first) == neighborDic.end()) {
            tailNodes.push_back(entry.first);
        }
    }
    sort(tailNodes.begin(), tailNodes.end());
    
    if (check(headNode, neighborDic, indegreeDic)) {
        cout << headNode << " ";
        for (int node : tailNodes) {
            cout << node << " ";
        }
        cout << endl;
    } else {
        cout << -1 << endl;
    }
    
    return 0;
}

C

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

#define MAX_NODES 1000

// 定义邻接表节点结构体
typedef struct Node {
    int value;
    struct Node *next;
} Node;

// 定义队列结构体
typedef struct Queue {
    int data[MAX_NODES];
    int front, rear;
} Queue;

// 队列初始化
void initQueue(Queue *q) {
    q->front = q->rear = 0;
}

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

// 入队
void enqueue(Queue *q, int value) {
    q->data[q->rear++] = value;
}

// 出队
int dequeue(Queue *q) {
    return q->data[q->front++];
}

// 添加邻接表边
void addEdge(Node **adjList, int from, int to) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->value = to;
    newNode->next = adjList[from];
    adjList[from] = newNode;
}

// 检查是否可以完成拓扑排序（是否存在环）
int check(int headNode, Node **adjList, int *indegree, int totalNodes) {
    Queue q;
    initQueue(&q);
    enqueue(&q, headNode);

    while (!isEmpty(&q)) {
        int curNode = dequeue(&q);
        Node *neighbor = adjList[curNode];
        while (neighbor) {
            indegree[neighbor->value]--;
            if (indegree[neighbor->value] == 0) {
                enqueue(&q, neighbor->value);
            }
            neighbor = neighbor->next;
        }
    }

    // 检查所有节点的入度是否为0
    for (int i = 0; i < totalNodes; i++) {
        if (indegree[i] != 0) {
            return 0; // 存在环
        }
    }
    return 1; // 无环
}

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

    Node *adjList[MAX_NODES] = {NULL}; // 邻接表
    int indegree[MAX_NODES] = {0};     // 入度表
    int nodes[MAX_NODES] = {0};        // 节点集合
    int nodeCount = 0;

    // 输入边并构建邻接表和入度表
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);

        addEdge(adjList, a, b);
        indegree[b]++;

        // 记录所有出现过的节点
        if (!nodes[a]) {
            nodes[a] = 1;
            nodeCount++;
        }
        if (!nodes[b]) {
            nodes[b] = 1;
            nodeCount++;
        }
    }

    int headNode = -1;
    for (int i = 0; i < MAX_NODES; i++) {
        if (nodes[i] && indegree[i] == 0) {
            headNode = i;
            break;
        }
    }

    // 找尾节点
    int tailNodes[MAX_NODES];
    int tailCount = 0;
    for (int i = 0; i < MAX_NODES; i++) {
        if (nodes[i] && adjList[i] == NULL) {
            tailNodes[tailCount++] = i;
        }
    }

    // 尾节点排序
    for (int i = 0; i < tailCount - 1; i++) {
        for (int j = 0; j < tailCount - i - 1; j++) {
            if (tailNodes[j] > tailNodes[j + 1]) {
                int temp = tailNodes[j];
                tailNodes[j] = tailNodes[j + 1];
                tailNodes[j + 1] = temp;
            }
        }
    }

    // 调用check函数
    if (check(headNode, adjList, indegree, MAX_NODES)) {
        printf("%d", headNode);
        for (int i = 0; i < tailCount; i++) {
            printf(" %d", tailNodes[i]);
        }
        printf("\n");
    } else {
        printf("-1\n");
    }

    // 释放邻接表内存
    for (int i = 0; i < MAX_NODES; i++) {
        Node *current = adjList[i];
        while (current) {
            Node *temp = current;
            current = current->next;
            free(temp);
        }
    }

    return 0;
}

Node JavaScript

const readline = require('readline');

// 检查是否能够完成拓扑排序（是否存在环）的函数
function check(headNode, neighborMap, indegreeMap) {
    const queue = [];
    queue.push(headNode);

    while (queue.length > 0) {
        const curNode = queue.shift();
        for (const nextNode of neighborMap.get(curNode) || []) {
            indegreeMap.set(nextNode, indegreeMap.get(nextNode) - 1);
            if (indegreeMap.get(nextNode) === 0) {
                queue.push(nextNode);
            }
        }
    }

    // 检查所有节点的入度是否均为0
    for (const value of indegreeMap.values()) {
        if (value !== 0) return false;
    }
    return true;
}

// 输入处理
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const inputLines = [];
rl.on('line', (line) => {
    inputLines.push(line.trim());
}).on('close', () => {
    const n = parseInt(inputLines[0]);
    const lst = inputLines[1].split(' ').map(Number);

    // 构建邻接表和入度表
    const neighborMap = new Map();
    const indegreeMap = new Map();

    for (let i = 0; i < 2 * n; i += 2) {
        const a = lst[i];
        const b = lst[i + 1];
        if (!neighborMap.has(a)) neighborMap.set(a, []);
        neighborMap.get(a).push(b);
        indegreeMap.set(b, (indegreeMap.get(b) || 0) + 1);
    }

    let headNode = -1;
    for (const k of neighborMap.keys()) {
        if (!indegreeMap.has(k)) {
            headNode = k;
            break;
        }
    }

    const tailNodes = [];
    for (const k of indegreeMap.keys()) {
        if (!neighborMap.has(k)) {
            tailNodes.push(k);
        }
    }
    tailNodes.sort((a, b) => a - b);

    // 调用拓扑排序检查函数
    if (check(headNode, neighborMap, indegreeMap)) {
        console.log(headNode, ...tailNodes);
    } else {
        console.log(-1);
    }
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "sort"
        "strconv"
        "strings"
)

// 检查是否能够完成拓扑排序（是否存在环）
func check(headNode int, neighborMap map[int][]int, indegreeMap map[int]int) bool {
        queue := []int{headNode}

        for len(queue) > 0 {
                curNode := queue[0]
                queue = queue[1:]

                for _, nextNode := range neighborMap[curNode] {
                        indegreeMap[nextNode]--
                        if indegreeMap[nextNode] == 0 {
                                queue = append(queue, nextNode)
                        }
                }
        }

        // 检查所有节点的入度是否均为0
        for _, v := range indegreeMap {
                if v != 0 {
                        return false
                }
        }
        return true
}

func main() {
        reader := bufio.NewReader(os.Stdin)

        // 读取边数
        line, _ := reader.ReadString('\n')
        n, _ := strconv.Atoi(strings.TrimSpace(line))

        // 读取边的输入
        line, _ = reader.ReadString('\n')
        edges := strings.Fields(line)
        lst := make([]int, len(edges))
        for i, v := range edges {
                lst[i], _ = strconv.Atoi(v)
        }

        // 构建邻接表和入度表
        neighborMap := make(map[int][]int)
        indegreeMap := make(map[int]int)

        for i := 0; i < 2*n; i += 2 {
                a, b := lst[i], lst[i+1]
                neighborMap[a] = append(neighborMap[a], b)
                indegreeMap[b]++
        }

        headNode := -1
        for k := range neighborMap {
                if _, exists := indegreeMap[k]; !exists {
                        headNode = k
                        break
                }
        }

        tailNodes := []int{}
        for k := range indegreeMap {
                if _, exists := neighborMap[k]; !exists {
                        tailNodes = append(tailNodes, k)
                }
        }
        sort.Ints(tailNodes)

        // 调用拓扑排序检查函数
        if check(headNode, neighborMap, indegreeMap) {
                fmt.Print(headNode)
                for _, v := range tailNodes {
                        fmt.Printf(" %d", v)
                }
                fmt.Println()
        } else {
                fmt.Println(-1)
        }
}

时空复杂度

时间复杂度：O(N)。

空间复杂度：O(N)。