输入无向图顶点信息和边信息，创建图的邻接矩阵存储结构，计算图的连通分量个数。
输入无向图顶点信息和边信息，创建图的邻接矩阵存储结构，计算图的连通分量个数。
测试次数t
每组测试数据格式如下：
第一行：顶点数 顶点信息
第二行：边数
第三行开始，每行一条边信息
每组测试数据输出，顶点信息和邻接矩阵信息
输出图的连通分量个数，具体输出格式见样例。
每组输出直接用空行分隔。
#include<iostream> #include<string> using namespace std; #define Maxlen 40 void DFS(int n,int v,bool *visit,int m[100][100]); int DFSmove(int n,bool *visit,int m[100][100]) { int Count=0; for(int i=0;i<Maxlen;i++) { visit[i]=false; } for(int i=0;i<n;i++) { if(visit[i]==false) { Count++; DFS(n,i,visit,m); } } return Count; } void DFS(int n,int v,bool *visit,int m[100][100]) { visit[v]=true; int *temp=new int[n];///找到与v相连的结点 for(int i=0;i<n;i++) temp[i]=-1; int k=0; for(int i=0;i<n;i++) { if(m[v][i]==1) { temp[k]=i; k++; } } int w; int i=0; for(w=temp[i];w>=0;i++,w=temp[i]) { if(visit[w]==false) DFS(n,w,visit,m); } delete []temp; } int main() { int T; cin>>T; while(T--) { int pn; cin>>pn; string *p=new string[pn]; for(int i=0;i<pn;i++) cin>>p[i]; int ln; cin>>ln; int m[100][100]; for(int i=0;i<pn;i++) for(int j=0;j<pn;j++) m[i][j]=0; int flag1,flag2; string p1,p2; for(int i=0;i<ln;i++) { cin>>p1>>p2; for(int j=0;j<pn;j++) { if(p[j]==p1) { flag1=j; } if(p[j]==p2) { flag2=j; } } m[flag1][flag2]=1; m[flag2][flag1]=1; } for(int i=0;i<pn;i++) { if(i!=pn-1) cout<<p[i]<<" "; else cout<<p[i]<<endl; } for(int i=0;i<pn;i++) { for(int j=0;j<pn;j++) { if(j==pn-1) cout<<m[i][j]; else cout<<m[i][j]<<" "; } cout<<endl; } int n=pn; bool visit[Maxlen]; cout<<DFSmove(n,visit,m)<<endl; if(T) cout<<endl; delete []p; } return 0; }
原文：https://www.cnblogs.com/SZU-DS-wys/p/12180937.html