跳转至

DS图—图的邻接矩阵存储及度计算

时间限制: 1 Sec 内存限制: 128 MB

题目描述

假设图用邻接矩阵存储。输入图的顶点信息和边信息,完成邻接矩阵的设置,并计算各顶点的入度、出度和度,并输出图中的孤立点(度为0的顶点)

--程序要求-- 若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件,不看代码,作0分处理 不允许使用第三方对象或函数实现本题的要求

输入

测试次数T,每组测试数据格式如下:

图类型 顶点数 (D—有向图,U—无向图)

顶点信息

边数

每行一条边(顶点1 顶点2)或弧(弧尾 弧头)信息

输出

每组测试数据输出如下信息(具体输出格式见样例):

图的邻接矩阵

按顶点信息输出各顶点的度(无向图)或各顶点的出度 入度 度(有向图)。孤立点的度信息不输出。

图的孤立点。若没有孤立点,不输出任何信息。

样例输入

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
2
D 5
V1 V2 V3 V4 V5
7
V1 V2
V1 V4
V2 V3
V3 V1
V3 V5
V4 V3
V4 V5
U 5
A B C D E
5
A B
A C
B D
D C
A D

样例输出

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
0 1 0 1 0
0 0 1 0 0
1 0 0 0 1
0 0 1 0 1
0 0 0 0 0
V1: 2 1 3
V2: 1 1 2
V3: 2 2 4
V4: 2 1 3
V5: 0 2 2
0 1 1 1 0
1 0 0 1 0
1 0 0 1 0
1 1 1 0 0
0 0 0 0 0
A: 3
B: 2
C: 2
D: 3
E

提示

解决方案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <vector>
#include <string>

class Map {
public:
    Map(const char type, const int size) : type_(type), size_(size), vector_(size),matrix_(size, std::vector<int>(size, 0)) {}
    void setFromCin() {
        for (int i = 0; i < size_; ++i) {
            std::cin >> vector_[i];
        }
        int size;
        std::cin >> size;
        for (int i = 0; i < size; ++i) {
            setMatFromCin();
        }
    }
    void printAllDegree() {
        for (int ir = 0; ir < matrix_.size(); ++ir) {
            std::cout << matrix_[ir].front();
            for (int ic = 1; ic < matrix_.size(); ++ic) {
                std::cout << ' ' << matrix_[ir][ic];
            }
            std::cout << std::endl;
        }
        if (type_ == 'D') {
            for (int i = 0; i < vector_.size(); ++i) {
                std::cout << vector_[i];
                int inDegree = 0, outDegree = 0;
                for (int ir = 0; ir < matrix_.size(); ++ir) {
                    if (matrix_[i][ir] == 1) {
                        inDegree += 1;
                    }
                }
                for (int ic = 0; ic < matrix_.size(); ++ic) {
                    if (matrix_[ic][i] == 1) {
                        outDegree += 1;
                    }
                }
                if (inDegree + outDegree != 0) {
                    std::cout << ": " << inDegree << ' ' << outDegree << ' ' << inDegree + outDegree << std::endl;
                }
            }
        } else if (type_ == 'U') {
            for (int i = 0; i < vector_.size(); ++i) {
                std::cout << vector_[i];
                int degree = 0;
                for (int ir = 0; ir < matrix_.size(); ++ir) {
                    if (matrix_[i][ir] == 1) {
                        degree += 1;
                    }
                }
                if (degree != 0) {
                    std::cout << ": " << degree << std::endl;
                }
            }
        }
    }
private:
    char type_;
    int size_;
    std::vector<std::string> vector_;
    std::vector<std::vector<int> > matrix_;
    void setMatFromCin() {
        std::string src, dst;
        std::cin >> src >> dst;
        for (int i1 = 0; i1 < vector_.size(); ++i1) {
            if (vector_[i1] == src) {
                for (int i2 = 0; i2 < vector_.size(); ++i2) {
                    if (vector_[i2] == dst) {
                        if (type_ == 'D') {
                            matrix_[i1][i2] = 1;
                        } else if (type_ = 'U') {
                            matrix_[i1][i2] = 1;
                            matrix_[i2][i1] = 1;
                        }
                        return;
                    }
                }
            }
        }
    }
};

int main() {
    int ctrl;
    std::cin >> ctrl;

    while (ctrl--) {
        char type;
        int size;
        std::cin >> type >> size;
        Map map(type, size);
        map.setFromCin();
        map.printAllDegree();
    }

    return 0;
}

评论