欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-21 08:49:09
...

题目:

问题 A: DS图—图的邻接矩阵存储及度计算
时间限制: 1 Sec  内存限制: 128 MB
提交: 558  解决: 292
[提交][状态][讨论版]
题目描述
假设图用邻接矩阵存储。输入图的顶点信息和边信息,完成邻接矩阵的设置,并计算各顶点的入度、出度和度,并输出图中的孤立点(度为0的顶点)

--程序要求--
若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件,不看代码,作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
测试次数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>
using namespace std;

int main(void)
{
    int i, j, k, t, s;
    cin>>t;
    while(t--)
    {
        char ch;
        int n;
        cin>>ch>>n;
        if('D'==ch)
        {
            string str1, str2;
            char a[n][10];
            int b[n][n];
            for(i=0; i<n; i++)
            {
                for(j=0; j<n; j++)
                {
                    b[i][j] = 0;
                }
            }
            int out[n];
            for(i=0; i<n; i++)
                out[i] = 0;
            int in[n];
            for(i=0; i<n; i++)
                in[i] = 0;
            for(i=0; i<n; i++)
                cin>>a[i];
            cin>>s;
            for(i=0; i<s; i++)
            {
                cin>>str1>>str2;
                for(j=0; j<n; j++)
                {
                    if(a[j]==str1)
                    {
                        out[j]++;
                        for(k=0; k<n; k++)
                        {
                            if(a[k]==str2)
                            {
                                in[k]++;
                                b[j][k] = 1;
                            }
                        }
                    }
                }
            }
            for(i=0; i<n; i++)
            {
                for(j=0; j<n; j++)
                {
                    if(j!=n-1)
                        cout<<b[i][j]<<' ';
                    else
                        cout<<b[i][j]<<endl;
                }
            }
            for(i=0; i<n; i++)
            {
                if(in[i]+out[i])
                    cout<<a[i]<<':'<<' '<<out[i]<<' '<<in[i]<<' '<<in[i]+out[i]<<endl;
            }
            for(i=0; i<n; i++)
            {
                if(!(in[i]+out[i]))
                    cout<<a[i]<<endl;
            }
        }
        else if('U'==ch)
        {
            string str1, str2;
            char a[n][10];
            int b[n][n];
            for(i=0; i<n; i++)
            {
                for(j=0; j<n; j++)
                {
                    b[i][j] = 0;
                }
            }
            int degree[n];
            for(i=0; i<n; i++)
                degree[i] = 0;
            for(i=0; i<n; i++)
                cin>>a[i];
            cin>>s;
            for(i=0; i<s; i++)
            {
                cin>>str1>>str2;
                for(j=0; j<n; j++)
                {
                    if(a[j]==str1)
                    {
                        degree[j]++;
                        for(k=0; k<n; k++)
                        {
                            if(a[k]==str2)
                            {
                                degree[k]++;
                                b[j][k] = 1;
                                b[k][j] = 1;
                            }
                        }
                    }
                }
            }
            for(i=0; i<n; i++)
            {
                for(j=0; j<n; j++)
                {
                    if(j!=n-1)
                        cout<<b[i][j]<<' ';
                    else
                        cout<<b[i][j]<<endl;
                }
            }
            for(i=0; i<n; i++)
            {
                if(degree[i])
                    cout<<a[i]<<':'<<' '<<degree[i]<<endl;
            }
            for(i=0; i<n; i++)
            {
                if(!degree[i])
                    cout<<a[i]<<endl;
            }
        }
    }
    return 0;
}

题解:

在输入顶点信息的时候,由于顶点可能不止一个字符表示,所以存储其要用字符串数组来存。字符串数组即二维字符数char a[i][j],在输入的时候循环对a[i]输入即可,则a[i]即代表每一个字符串。

相关标签: 数据结构