Задача на Графы(Элементарные алгоритмы)

Revision ru1, by C4RU, 2019-03-18 07:58:55

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

Ограничение по времени: 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)

Tags задача, графы

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian C4RU 2019-03-18 07:58:55 1531 Первая редакция (опубликовано)