Cod sursa(job #1168097)

Utilizator cosminpdrfischer2004 cosminp Data 6 aprilie 2014 22:09:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdlib>
#include <fstream>
#include <vector>

using namespace std;


void dfs(int node, vector< vector<int> > &neighbors, vector<int> &visited)
{
    visited[node] = 1;
    for (vector<int>::iterator it = neighbors[node].begin(); it != neighbors[node].end(); it++)
    {
        if (!visited[*it]) dfs(*it, neighbors, visited);
    }
}


int main()
{
    vector< vector<int> >   neighbors;
    vector<int>             visited;
    int                     M, N, a, b;
    int                     componentCount;
    fstream                 f, g;

    f.open("dfs.in", ios::in);
    g.open("dfs.out", ios::out);

    f >> N >> M;
    neighbors.resize(N);
    visited.resize(N, 0);
    for (int i = 0; i < M; i++)
    {
        f >> a >> b;
        a--; b--;
        neighbors[a].push_back(b);
        neighbors[b].push_back(a);
    }

    componentCount = 0;
    for (int i = 0; i< N; i++)
    {
        if (!visited[i])
        {
            componentCount++;
            dfs(i, neighbors, visited);
        }
    }

    g << componentCount;

    f.close();
    g.close();

    return 0;
}