Cod sursa(job #1550220)

Utilizator Gaci27Horvat Catalin Gaci27 Data 13 decembrie 2015 13:38:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;

int n, m, a, b;  				//nr. de noduri/muchii
bool vizitat[nmax];			//vizitat[]
vector <int> v[nmax];		//listele de vecini

void dfs(int node) {
		vizitat[node] = true;
    
    for(auto vecin:v[node]) //C++11 (versiune mai noua)
    		if(!vizitat[vecin])
        		dfs(vecin);
}


int main() {								//begin
		ifstream f("dfs.in");		//assign f('dfs.in'); reset(f);
    ofstream g("dfs.out");	//assign g('dfs.out'); rewrite(g);
    
    f >> n >> m; 						//read(f, n, m);
    //puteam si f>>n; f>>m;
    for(int i=1; i<=m; i++) {
    		f >> a >> b;
        v[a].push_back(b);	//b e vecin al lui a
        v[b].push_back(a);	//a e vecin al lui b
    }
    
    int componente = 0;
    for(int i=1; i<=n; i++)
    		if(!vizitat[i]) {
        		componente++;
            dfs(i);						//dfs(i) viziteaza toata componenta conexa a nodului i
        }
        
    g << componente << "\n";  //writeln(g, componente);
    return 0;
}