Cod sursa(job #1087357)

Utilizator varga13VarGaz13 varga13 Data 19 ianuarie 2014 12:24:26
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>
#define mx 100000
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int n, m,k ;
bool sol[mx];
vector<int> nods[mx];

void read()
{
    f>>n>>m;
    for(int i=0;i<m;++i)
    {
        int aux1, aux2;
        f>>aux1>>aux2;
        nods[aux1].push_back(aux2);
        nods[aux2].push_back(aux1);
    }
}

void Dfs(int nod)
{

    sol[nod]=1;
    for(int i=0;i<nods[nod].size();++i)
    {
        if(!sol[nods[nod][i]])
            Dfs(nods[nod][i]);
    }
}

int main()
{
    read();
    for(int i=1;i<=n;i++)
    {
        if(!sol[i])
            k++,Dfs(i);
    }
    g<<k;
    f.close();
    g.close();
    return 0;
}