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<cstring>
using namespace std;
 
int find(string str[], string st, int n){
    for(int i= 0; i< n; i++)
      if(str[i]== st)
       return i;
}
 
int main(){
    int t;
    cin>>t;
     
    while(t--){
         
        int n;
        cin>>n;
         
        string str[200];
        for(int i= 0; i< n; i++)
           cin>>str[i];
            
 
        int array[n+ 5][n+5];
         
        for(int i= 0; i< n+ 5; i++)
          for(int j= 0 ; j< n+ 5; j++)
            array[i][j]= 0;
             
        int in;
        cin>>in;
         
        for(int i= 0 ; i< in; i++){
            string s1; 
            string s2;
            cin>>s1>>s2;
             
            int a= find(str, s1, n);
            int b= find(str, s2, n);
             
            array[a][b]= 1;
             
            array[b][a]= 1;
        }
         
        for(int i= 0; i< n; i++){
            cout<<str[i];
            if(i!= n- 1)
              cout<<" ";
        }
        cout<<endl;
        for(int i= 0; i< n; i++){
          for(int j= 0; j< n; j++){
            cout<<array[i][j];    
            if(j!= n- 1)
             cout<<" ";       
          }
 
            cout<<endl;
        }
         
         
        int arr[n+ 5];
        for(int i= 0; i< n+ 5; i++)
          arr[i]= i;
           
          for(int i= 0; i< n; i++){
             
            for(int j= 0; j< n ;j++){
                if(array[i][j]){
                     
                    for(int k= 0; k< n;k++)
                      if(arr[k]== arr[i])
                        arr[k]= arr[j];
                         
                  }
              }
          }
         
//      for(int i= 0; i< n; i++){
//          cout<<arr[i]<<"--";
//      }
//      cout<<endl;
         
        int shu[n+ 5];
        for(int i= 0; i< n ;i++)
          shu[i]= 0;
           
        for(int i= 0; i< n+ 5; i++)
          shu[arr[i]]++;
         
        int sum= 0;
         
        for(int i= 0; i< n; i++){
            if(shu[i])
             sum++;
        }
         
        cout<<sum<<endl<<endl;
        }
 
     
     
    return 0;
}