Компоненты связности
Ограничение по времени: 2 секунды Ограничение по памяти: 64 мегабайта ~~~~~ Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности.
Формат входного файла В первой строке входного файла содержится одно натуральное число N (N ≤ 100) — количество вершин в графе. Далее в N строках по N чисел — матрица смежности графа: в i-й строке на j-м месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.
Формат выходного файла Вывести одно целое число — искомое количество компонент связности графа.
- 6
- 0 1 1 0 0 0
- 1 0 1 0 0 0
- 1 1 0 0 0 0
- 0 0 0 0 1 0
- 0 0 0 1 0 0
- 0 0 0 0 0 0
- 3 ~~~~~
Я решил с :**DFS и список смежности**
КОД
#include <bits/stdc++.h>
using namespace std;
int was[100],n,a,ans;
vector <int> g[100];
int dfs(int v){
was[v]=1;
for(auto to : g[v]){
if(was[to]==0){
dfs(to);
}
}
return 0;
}
int main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
cin>>n;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
cin>>a;
if(a==1){
g[i].push_back(j);
g[j].push_back(i);
}
}
}
for(int i = 0; i<n; i++){
if(was[i]==0){
dfs(i);
ans++;
}
}
cout<<ans;
return 0;
}