邻接表与邻接矩阵
题目代码
题目
题目：邻接表和邻接矩阵都是图的表示方法，它们相互之间也可以通过一定的方式进行转换。本题将给出一个有向图的邻接表，请将此邻接表转换成对应的邻接矩阵。
说明：每个点由除空格外的一个可显示字符表示，点的顺序由ASCII码表的顺序决定。
输入：输入有若干行每行的第一个字符表示起点，随后由空格隔开的若干字符表示终点
输出：该邻接表对应的邻接矩阵（字符在邻接表中未出现表示不含该点）
测试输入
期待的输出
时间限制
内存限制
额外进程
测试用例 1以文本方式显示
a b c↵b a c↵c a b↵
以文本方式显示
0 1 1↵1 0 1↵1 1 0↵
1秒64M0
代码
#include<cstdio>
#include<string.h>
#include<map>
#include<algorithm>
#include<vector>
char linjiebiao
[150][150];
int zhen
[150][150];
using namespace std
;
map
<char, int> Point
;
map
<char, int> points
;
typedef pair
<char, int> PAIR
;
int cmp(const PAIR
& x
, const PAIR
& y
)
{
return x
.first
> y
.first
;
}
int main()
{
int len
= 0;
int row
= 0;
char Row
[20];
int index
;
int i
,j
,k
;
while (gets(linjiebiao
[row
]) != NULL)
{
for (i
= 0; linjiebiao
[row
][i
]; i
++)
{
if (linjiebiao
[row
][i
] != ' ')
{
char c
= linjiebiao
[row
][i
];
if (points
.count(c
) == 0)
{
points
.insert(pair
<char, int>(c
, 0));
}
if (Point
.count(c
) == 0)
{
Point
.insert(pair
<char, int>(c
, 0));
}
}
}
if (len
< Point
.size())
{
len
= Point
.size();
}
Point
.clear();
row
++;
}
map
<char, int>::iterator it
= points
.begin();
int value
= 0;
while (it
!= points
.end())
{
it
->second
= value
++;
it
++;
}
for (i
= 0; i
< row
; i
++)
{
int a
= points
.find(linjiebiao
[i
][0])->second
;
for (int j
= 1; linjiebiao
[i
][j
]; j
++)
{
if (linjiebiao
[i
][j
] != ' ')
{
int b
= points
.find(linjiebiao
[i
][j
])->second
;
zhen
[a
][b
]++;
}
}
}
len
= points
.size();
for (i
= 0; i
< len
; i
++)
{
for (j
= 0; j
< len
; j
++)
{
if (j
== len
- 1)
{
printf("%d\n", zhen
[i
][j
]);
}
else
{
printf("%d ", zhen
[i
][j
]);
}
}
}
}
