Cod sursa(job #1025828)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 10 noiembrie 2013 16:38:14
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>

using namespace std;

struct node
{
	int edge;
	node *next;

	node (int x)
	{
		edge = x;
		next = NULL;
	}
};


void add(node *&root, int x)
{
	node *aux = new node(x);
	aux->next = root;
	root = aux;
}

vector < pair < node *, int > > A;

void dfs(int x)
{
	A[x].second = 1;
	for (node *p = A[x].first; p; p = p->next)
		if (!A[p->edge].second)
			dfs(p->edge);
}

int main()
{
	int n, m, a, b;
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");

	fin>>n>>m;
	for (int i = 0; i <= n; ++i)
		A.push_back(make_pair( (node *) (NULL), 0));
	for (int i = 0; i < m; ++i)
	{
		fin>>a>>b;
		add(A[a].first, b);
	}

	int sol = 0;
	for (int i = 1; i <= n; ++i)
		if (!A[i].second)
		{
			dfs(i);
			++sol;
		}
	fout<<sol<<endl;
	return 0;
}