题目描述
假设无向图G采用邻接矩阵存储，编写一个算法求连通分量的个数。
输入
第一行为一个整数n，表示顶点的个数（顶点编号为0到n-1），接下来是为一个n*n大小的整数矩阵，表示图的邻接关系。数字为0表示不邻接，1表示不邻接。
输出
连通分量的个数。
样例输入
5
0 1 0 1 1
1 0 1 1 0
0 1 0 1 1
1 1 1 0 1
1 0 1 1 0
样例输出
1
#include <iostream> using namespace std; int n, ans; const int N = 1010; int g[N][N],st[N]; void dfs(int x, int y) { st[x] = st[y] = 1; for(int i = 0; i < n; i++) if(!st[i]) dfs(y ,i); } int main() { cin>>n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin>>g[i][j]; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(g[i][j]&&!st[i]){ dfs(i, j); ans++; } } } cout<<ans; return 0; }
