Cod sursa(job #1473607)

Utilizator IulianBoboUAIC Boboc Iulian IulianBobo Data 19 august 2015 19:08:59
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<iostream>
#include<fstream>
using namespace std;

#define MAX_N 100001

ifstream fin("dfs.in");
ofstream fout("dfs.out");

typedef struct nodes
{
	int nod;
	struct nodes *next;
} Nodes;

Nodes *node[MAX_N];
int n, m, nr, vizitat[MAX_N];

void add(int a, int b)
{
	Nodes *temp = new nodes;
	temp->nod = b;
	temp->next = node[a];
	node[a] = temp;
}

void readData()
{
	int a, b;
	fin >> n >> m;
	for (int i = 0; i < m; i++){
		fin >> a >> b;
		add(a, b);
	}
	fin.close();
}

void dfs(int nod)
{
	vizitat[nod] = nr;
	for (Nodes *it = node[nod]; it; it = it->next){
		dfs(it->nod);
	}
}

void compute()
{
	for (int i = 1; i <= n; i++){
		vizitat[i] = -1;
	}

	for (int i = 1; i <= n; i++){
		if (vizitat[i] == -1){
			dfs(i);
			++nr;
		}
	}

	fout << nr;

	fout.close();
}

int main()
{
	readData();
	compute();
	return 0;
}