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

题目描述

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

–程序要求–
若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件，不看代码，作0分处理
不允许使用第三方对象或函数实现本题的要求
ps:(我们老师允许让我们用string????)

输入

测试次数T，每组测试数据格式如下：

图类型 顶点数 （D—有向图，U—无向图）

顶点信息

边数

每行一条边（顶点1 顶点2）或弧（弧尾 弧头）信息

输出

每组测试数据输出如下信息（具体输出格式见样例）：

图的邻接矩阵

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

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

样例输入

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

样例输出

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

#include <iostream>
#include <string>
using namespace std;

class Graph{
    char type;
    int vexNum;
    int arcNum;
    string *vex;
    int **array;
    int *in;
    int *out;
public:
    Graph();
    ~Graph();
    int Index(string str);
    void countDegree();
    void outPut();
};

Graph::Graph() {
    cin>>type>>vexNum;

    vex = new string[vexNum];
    for(int i=0;i<vexNum;i++)
        cin>>vex[i];

    array = new int*[vexNum];
    for(int i=0;i<vexNum;i++) {
        array[i] = new int[vexNum];
        for(int j=0;j<vexNum;j++)
            array[i][j] = 0;
    }

    in = new int[vexNum];
    out = new int[vexNum];
    for(int i=0;i<vexNum;i++)
    {
        in[i]=0;
        out[i]=0;
    }

    cin>>arcNum;
    for(int i=0;i<arcNum;i++)
    {
        string str1,str2;
        cin>>str1>>str2;
        int pos1=Index(str1),pos2=Index(str2);
        if(type == 'U')
        {
            array[pos1][pos2] = 1;
            array[pos2][pos1] = 1;
        }
        else if(type == 'D')
            array[pos1][pos2] = 1;
    }
}

Graph::~Graph() {
    for(int i=0;i<vexNum;i++)
        delete array[i];

    delete array;
    delete in;
    delete out;
}

int Graph::Index(string str) {
    for(int i=0;i<vexNum;i++)
        if(vex[i] == str)
            return i;
    return -1;
}

void Graph::countDegree() {
    for(int i=0;i<vexNum;i++)
        for(int j=0;j<vexNum;j++)
            if(array[i][j] == 1)
            {
                out[i]++;
                in[j]++;
            }


}

void Graph::outPut() {
    for(int i=0;i<vexNum;i++)
        for (int j = 0; j < vexNum; j++)
            if (j != vexNum - 1)
                cout << array[i][j] << ' ';
            else
                cout << array[i][j] << endl;

    for(int i=0;i<vexNum;i++)
    {
        cout<<vex[i];
        if(type=='D')
            if(out[i]!=0 || in[i]!=0)
                cout<<": "<<out[i]<<' '<<in[i]<<' '<<out[i]+in[i]<<endl;
            else
                cout<<endl;
        else if(type == 'U')
            if(out[i]!=0)
                cout<<": "<<in[i]<<endl;
            else
                cout<<endl;
    }
}

int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        Graph myGraph;
        myGraph.countDegree();
        myGraph.outPut();
    }
    return 0;
}