题目描述
给定一个图的邻接矩阵，请判断该图是否是连通图。连通图：任意两个顶点之间都有路径。
输入
第1行输入一个整数k，表示有k个测试数据
第2行输入一个整数n，表示有n个结点
从第3行起到第n+2行输入一个邻接矩阵，其中Matrix[i,j]=1表示第i，j个结点之间有边，否则不存在边。
接下来是第2到第k个测试数据的结点数和邻接矩阵
输出
输出Yes or No表示图是否是强连通图
样例输入
2
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
7
0 1 0 0 0 0 0
0 0 1 1 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 0 0 1 0 1 0
样例输出
Yes
No
这道题只需对每一个顶点调用一次深度遍历，设置一个count，对于每个顶点，遍历前count=0，判断遍历后count==vexnum ？ 若对于每一个顶点都有count==vexnum就说明这个图是强连通的
#includeusing namespace std;const int MaxLen = 20;class Map{private: bool Visit[MaxLen]; int Matrix[MaxLen][MaxLen]; int Vexnum; void DFS(int v) { int w, i, k; Visit[v] = true; count1++; //cout< <<" "; //寻找邻接点 int *AdjVex = new int[Vexnum]; for (i = 0; i < Vexnum; i++) AdjVex[i] = -1; k = 0; for (i = 0; i < MaxLen; i++) if (Matrix[v][i] == 1) AdjVex[k++] = i; i = 0; for (w = AdjVex[i++]; w >= 0; w = AdjVex[i++]) { if (Visit[w] == false) DFS(w); } delete[]AdjVex; }public: int count1; void SetMatrix(int vnum, int mx[MaxLen][MaxLen]) { 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]; } void DFSTraverse() { int v, i; for (i = 0; i < Vexnum; i++) Visit[i] = false; for (v = 0; v < Vexnum; v++) if (!Visit[v]) DFS(v); cout << endl; } int lt() { int i, j; for (i = 0; i < Vexnum; i++) { for (j = 0; j < Vexnum; j++) Visit[j] = false; count1 = 0; DFS(i); if (count1 != Vexnum) return 0; } return 1; }};int main(){ int t; cin >> t; while (t--) { int n, i, j; cin >> n; int a[MaxLen][MaxLen]; for (i = 0; i < n; i++) for (j = 0; j < n; j++) cin >> a[i][j]; Map map; map.SetMatrix(n, a); if (map.lt()) cout << "Yes" << endl; else cout << "No" << endl; }}