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]即代表每一个字符串。
上一篇: 图的邻接矩阵存储