Cod sursa(job #1001116)

Utilizator alexx.cosmaCosma Cristian Alexandru alexx.cosma Data 24 septembrie 2013 15:37:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int N,M;

const int maxN = 100010;

vector<int>adj[maxN];

int vis[maxN];

void dfs();
void dfs(int i);
int main()
{
    fin>>N;
    fin>>M;
    for(int i=0; i<M; i++)
    {
        int source,dest;
        fin>>source;
        fin>>dest;
        adj[source].push_back(dest);
        adj[dest].push_back(source);
    }
    dfs();
    return 0;
}

void dfs()
{
    int nrConexe =0;
    for(int i=1; i<=N; i++)
    {
        if(vis[i]==0)
        {
            dfs(i);
            nrConexe++;
        }
    }
    fout<<nrConexe<<'\n';
}

void dfs(int nod){
    vis[nod]=1;
    int nrNeigh = adj[nod].size();
    for(int i=0;i<nrNeigh;i++){
        if(vis[adj[nod][i]]==0){
            dfs(adj[nod][i]);
        }
    }
}