Cod sursa(job #1705884)

Utilizator roby10roby10 roby10 Data 21 mai 2016 01:28:51
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <cstdio>
#include <vector>

#define Nmax 100002

using namespace std;

long int N,M;
long vizitat[Nmax];

vector< vector<long> > adj_mat(Nmax, vector<long>());

void dfs(long s)
{
	vizitat[s] = 1;

	for(long i = 0 ; i < adj_mat[s].size(); i++)
	{
		if(!vizitat[adj_mat[s][i]])		
			dfs(adj_mat[s][i]);
	}
}

int main()
{
	FILE *fin = fopen("dfs.in", "r");
	FILE *fout = fopen("dfs.out" , "w");

	fscanf(fin, "%li %li", &N, &M);

	long comp_con = 0;

	for(long i = 0 ; i < M; i++)
	{
		long a,b;
		fscanf(fin, "%li %li", &a , &b);
		adj_mat[a].push_back(b);
	}

	for(long i = 1; i <= N; i++)
	{
		if(!vizitat[i])
		{
			dfs(i);
			comp_con++;
		}
	}


	fprintf(fout , "%li\n", comp_con);



	fclose(fin);
	fclose(fout);
}