SWUSTOJ #1065 无向图的连通分量计算

SWUSTOJ #1065 无向图的连通分量计算

  • 题目
    • 输入
    • 输出
    • 样例输入
    • 样例输出
  • 源代码

题目

假设无向图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>
#include <vector>using namespace std;int main()
{int flag = 0;int temp[1000];int count = 0;int n;cin >> n;for (int i = 0; i < n; i++){temp[i] = 0;}int arr[100][100];for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){cin >> arr[i][j];}}for (int i = 0, k = 1; i < n - 1; i++, k++){for (int j = k; j < n; j++){if (arr[i][j] != -1){if (flag == 0){temp[i] = 1;temp[j] = 1;flag = 1;}else{if (temp[i] == 0 && temp[j] == 0){temp[i] = 1;temp[j] = 1;count++;}}}}}cout << count;return 0;
}