题目链接

图的分类

题目描述

给定一个包含 台计算机和 条网线的连通网络。判断该网络的拓扑结构是链型 (line)、环型 (ring)、星型 (star)，还是不属于以上三类的未知结构 (unknown)。

解题思路

本题的核心是根据图中节点的度数分布来对图进行分类。一个节点的“度”是指与该节点直接相连的边的数量。由于题目保证图是连通的，我们可以通过统计所有节点的度数，来总结出每种特定结构的独有特征。

1. 结构特征分析

  • 链型 (line):

    • 一条链有 个节点，必然有 条边。

    • 度数分布：恰好有两个度为 的节点（链的两端），以及 个度为 的节点（链的中间部分）。

  • 环型 (ring):

    • 一个环有 个节点，必然有 条边。

    • 度数分布：所有 个节点的度都恰好为 。

  • 星型 (star):

    • 一个星型图有 个节点，必然有 条边。

    • 度数分布：恰好有一个度为 的中心节点，以及 个度为 的叶子节点。

  • 未知结构 (unknown):

    • 不满足以上任何一种特征的连通图。

2. 算法流程

  1. 计算度数：

    • 创建一个大小为 的数组 ，用于存储每个节点的度。

    • 遍历输入的 条边，对于每条边 ，将 和 的值分别加一。

  2. 统计度数分布：

    • 创建一个哈希表（map 或 dictionary），用于统计不同度数的节点数量。

    • 遍历节点 到 ，对于每个节点 ，将其度数 作为键，在 中对应的值加一。

  3. 模式匹配：

    • 根据前述的结构特征，检查 是否符合某种模式。

    • 判断环型：检查是否 并且 。

    • 判断链型：检查是否 并且 且 。

    • 判断星型：检查是否 并且 且 。

    • 如果以上都不满足，则为未知结构。

代码

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<int> degree(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        degree[u]++;
        degree[v]++;
    }

    map<int, int> degree_counts;
    for (int i = 1; i <= n; ++i) {
        degree_counts[degree[i]]++;
    }

    if (m == n && degree_counts.size() == 1 && degree_counts[2] == n) {
        cout << "ring\n";
    } else if (m == n - 1 && degree_counts.size() == 2 && degree_counts[1] == 2 && degree_counts[2] == n - 2) {
        cout << "line\n";
    } else if (m == n - 1 && degree_counts.size() == 2 && degree_counts[1] == n - 1 && degree_counts[n - 1] == 1) {
        cout << "star\n";
    } else {
        cout << "unknown\n";
    }

    return 0;
}

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

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

        int[] degree = new int[n + 1];
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            degree[u]++;
            degree[v]++;
        }

        Map<Integer, Integer> degreeCounts = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            degreeCounts.put(degree[i], degreeCounts.getOrDefault(degree[i], 0) + 1);
        }

        if (m == n && degreeCounts.size() == 1 && degreeCounts.getOrDefault(2, 0) == n) {
            System.out.println("ring");
        } else if (m == n - 1 && degreeCounts.size() == 2 && degreeCounts.getOrDefault(1, 0) == 2 && degreeCounts.getOrDefault(2, 0) == n - 2) {
            System.out.println("line");
        } else if (m == n - 1 && degreeCounts.size() == 2 && degreeCounts.getOrDefault(1, 0) == n - 1 && degreeCounts.getOrDefault(n - 1, 0) == 1) {
            System.out.println("star");
        } else {
            System.out.println("unknown");
        }
    }
}

import sys
from collections import Counter

def solve():
    line = sys.stdin.readline()
    if not line: return
    n, m = map(int, line.split())
    
    degree = [0] * (n + 1)
    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        degree[u] += 1
        degree[v] += 1
    
    # 使用Counter来统计度数分布
    degree_counts = Counter(degree[1:])

    if m == n and len(degree_counts) == 1 and degree_counts.get(2) == n:
        print("ring")
    elif m == n - 1 and len(degree_counts) == 2 and degree_counts.get(1) == 2 and degree_counts.get(2) == n - 2:
        print("line")
    elif m == n - 1 and len(degree_counts) == 2 and degree_counts.get(1) == n - 1 and degree_counts.get(n - 1) == 1:
        print("star")
    else:
        print("unknown")

solve()

算法及复杂度

  • 算法：计算并统计节点度数分布，进行模式匹配。

  • 时间复杂度：。

    • 读入 条边并计算所有节点的度，需要 的时间。

    • 遍历 个节点来统计度数分布，需要 的时间。

    • 模式匹配是常数时间操作。

    • 总体时间复杂度为 。

  • 空间复杂度：。

    • 需要一个大小为 的数组来存储每个节点的度数。

    • 统计度数分布的哈希表最多存储 个键值对。