Cod sursa(job #2128934)

Utilizator petrea1551Petrea Calin petrea1551 Data 12 februarie 2018 12:02:53
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>
using namespace std;

typedef struct Lista
{
	int val;
	Lista *next;
} lista;

bool viz[5000];
lista *v[5000];

void add(lista *&stiva, int data)
{
	lista *tmp = new lista;
	tmp->next = stiva;
	tmp->val = data;
	stiva = tmp;
}

void dfs(int n)
{
	viz[n] = 1;
	lista *tmp = v[n];
	while (tmp != NULL)
	{
		if (viz[tmp->val] == 0)
			dfs(tmp->val);
		tmp = tmp->next;
	}
}

int main()
{
	ifstream cin("dfs.in");
	ofstream cout("dfs.out");
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		add(v[x - 1], y - 1);
		add(v[y - 1], x - 1);
	}
	int k = 0;
	for (int i = 0; i < n; i++)
		if (viz[i] == 0)
		{
			k++;
			dfs(i);
		}
	cout << endl << k;
}