题目描述
输入无向图顶点信息和边信息，创建图的邻接矩阵存储结构，计算图的连通分量个数。
输入
测试次数t
每组测试数据格式如下：
第一行：顶点数 顶点信息
第二行：边数
第三行开始，每行一条边信息
输出
每组测试数据输出，顶点信息和邻接矩阵信息
输出图的连通分量个数，具体输出格式见样例。
每组输出直接用空行分隔。
输入样例1
3 4 A B C D 2 A B A C 6 V1 V2 V3 V4 V5 V6 5 V1 V2 V1 V3 V2 V4 V5 V6 V3 V5 8 1 2 3 4 5 6 7 8 5 1 2 1 3 5 6 5 7 4 8
输出样例1
A B C D 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 2 V1 V2 V3 V4 V5 V6 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 2 3 4 5 6 7 8 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 3
思路分析
建立邻接矩阵，用DFS的方式遍历图，如果只需要从一个节点出发就能遍历所有节点，那么只有一个联通分量，如果需要从多个节点出发才能遍历完所有节点，那么有多个联通分量。
因此，解决方式就是，从所有节点出发DFS，每遍历一个节点就标记下来，即不会遍历已遍历的节点，那么联通分量的数目就是需要DFS节点的数目。
AC代码
代码语言：javascript复制#include<iostream>
using namespace std;
const int MaxLength = 100;
struct Vertex {
int index;
string data;
} vertex[MaxLength];
class Map {
bool visited[MaxLength] = {false};
int matrix[MaxLength][MaxLength] = {0};
int vertexNumber;
int connectedComponent = 0, tempCount;
public:
Map() {
connectedComponent = 0;
cin >> vertexNumber;
for (int i = 0; i < vertexNumber; i ) {
cin >> vertex[i].data;
vertex[i].index = i;
}
int edgeNumber;
cin >> edgeNumber;
for (int i = 0; i < edgeNumber; i ) {
string tail, head;
cin >> tail >> head;
matrix[GetIndex(tail)][GetIndex(head)] = matrix[GetIndex(head)][GetIndex(tail)] = 1;
}
for (int i = 0; i < vertexNumber; i ) {
tempCount = 0;
if(!visited[i])
DFS(i);
if (tempCount>=1)
connectedComponent ;
}
}
int GetIndex(string &data) {
for (int i = 0; i < vertexNumber; i )
if (vertex[i].data == data)
return i;
}
void Show() {
for (int i = 0; i < vertexNumber - 1; i )
cout << vertex[i].data << ' ';
cout << vertex[vertexNumber - 1].data << endl;
for (int i = 0; i < vertexNumber; i ) {
for (int j = 0; j < vertexNumber - 1; j )
cout << matrix[i][j] << ' ';
cout << matrix[i][vertexNumber - 1] << endl;
}
cout << connectedComponent << endl << endl;
}
void DFS(int current) {
if (visited[current])
return;
visited[current] = true;
tempCount ;
for (int i = 0; i < vertexNumber; i )
if (matrix[current][i])
DFS(i);
}
};
int main() {
int t;
cin >> t;
while (t--) {
Map test;
test.Show();
}
}
