Cod sursa(job #1477145)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 25 august 2015 16:24:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <queue>
#include <fstream>
#include <iostream>
#include <cstdlib>

using namespace std;

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

vector <int> L[200009];

int n,m,viz[100009];

void Citire()
{
	int x,y,i;
	fin >> n; // numarul de noduri
	fin >> m; // nr de muchii
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y;
		L[x].push_back(y);
		L[y].push_back(x); //dispare daca e digraf (orientat)
    }
}


void DFS(int k)
{
    int i,j;
    viz[k] = 1;
	for (j = 0; j < L[k].size(); j++)
	{
		i = L[k][j];
		if (!viz[i]) DFS(i);
    }
}


int main ()
{
	int i,nrCompConexe;
    Citire();
    nrCompConexe = 0;
    for (i = 1; i <= n; i++)
	if (!viz[i]) { nrCompConexe++; DFS(i);}
    fout<<nrCompConexe<<"\n";
    fin.close();
    fout.close();
    return 0;
}