DS图—图的连通分量

题目描述

输入无向图顶点信息和边信息，创建图的邻接矩阵存储结构，计算图的连通分量个数。

输入

测试次数t

每组测试数据格式如下：

第一行：顶点数 顶点信息

第二行：边数

第三行开始，每行一条边信息

输出

每组测试数据输出，顶点信息和邻接矩阵信息

输出图的连通分量个数，具体输出格式见样例。

每组输出直接用空行分隔。

样例输入

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

样例输出

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

 

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

const int MaxLen =20;
class Map{
private:
    bool Visit[MaxLen];
    int Matrix[MaxLen][MaxLen];
    int Vexnum;
    void BFS(int v);
public:
    void SetMatrix(int vnum,int **mx);
    void BFSTraverse();
    int get();
};
void Map::BFSTraverse()
{
    cout<<0<<' ';
    Visit[0]=true;
    BFS(0);
    cout<<endl;
}
void Map::BFS(int v)
{
    Visit[v]=true;
    queue<int> Q;
    for(int i=0;i<Vexnum;i++)
    {
        if(Matrix[v][i]!=0 &&!Visit[i])
        {
            Q.push(i);
        }
    }
    while(!Q.empty())
    {
        BFS(Q.front());
        Q.pop();
    }
}
void Map::SetMatrix(int vnum,int **mx)
{
    for(int i=0;i<Vexnum;i++)
        Visit[i]=false;
    int i,j;
    Vexnum =vnum;
    for(i=0;i<MaxLen;i++)
        for(j=0;j<MaxLen;j++)
            Matrix[i][j]=0;
    for(i=0;i<Vexnum;i++)
        for(j=0;j<Vexnum;j++)
            Matrix[i][j]=mx[i][j];
}
int Map::get()
{
    int sum=0;
    for(int i=0;i<Vexnum;i++)
    {
        if(!Visit[i])
        {
            BFS(i);
            sum++;
        }
    }
    return sum;
}
void test()
{
    int n,k;
    cin>>n;
    string *s=new string[n];
    for(int i=0;i<n;i++)
        cin>>s[i];
    int **m;
    m=new int*[n];
    for(int i=0;i<n;i++)
    {
        m[i]=new int[n];
        for(int j=0;j<n;j++)
            m[i][j]=0;
    }
    cin>>k;
    string temp1,temp2;
    int flag1,flag2;
    for(int i=0;i<k;i++)
    {
        cin>>temp1>>temp2;
        for(int p=0;p<n;p++)
        {
            if(s[p]==temp1)
                flag1=p;
            if(s[p]==temp2)
                flag2=p;
        }
        m[flag1][flag2]=1;
        m[flag2][flag1]=1;
    }
    for(int i=0;i<n;i++)
    {
        if(i==n-1)
            cout<<s[i];
        else
            cout<<s[i]<<' ';
    }
    cout<<endl;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(j==n-1)
                cout<<m[i][j];
            else
            cout<<m[i][j]<<' ';
        }
        cout<<endl;
    }
    Map t;
    t.SetMatrix(n,m);
    cout<<t.get()<<endl<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
        test();
}