C4RU's blog

By C4RU, history, 5 years ago, In Russian

Компоненты связности

Ограничение по времени: 2 секунды Ограничение по памяти: 64 мегабайта ~~~~~ Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности.

Формат входного файла В первой строке входного файла содержится одно натуральное число N (N ≤ 100) — количество вершин в графе. Далее в N строках по N чисел — матрица смежности графа: в i-й строке на j-м месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.

Формат выходного файла Вывести одно целое число — искомое количество компонент связности графа.

  1. 6
  2. 0 1 1 0 0 0
  3. 1 0 1 0 0 0
  4. 1 1 0 0 0 0
  5. 0 0 0 0 1 0
  6. 0 0 0 1 0 0
  7. 0 0 0 0 0 0
  8. 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;
}

ПЛЗ помогите найти задачу про топологическую сортировку (Желательно на Codeforces)

  • Vote: I like it
  • -4
  • Vote: I do not like it