Cod sursa(job #2016810)

Utilizator cristian_99Olaru Cristian cristian_99 Data 30 august 2017 14:57:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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

const int NodMax = 100005;
vector < int > v[NodMax];

int n,m,cc;
bool viz[NodMax];

void read()
{
    fin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int a,b;
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
}

void dfs(int nod)
{
    viz[nod]=1;
    vector < int > ::iterator it;
    for (it=v[nod].begin(); it!=v[nod].end(); ++it)
        if(!viz[*it])
            dfs(*it);
}


int main()
{
    read();
    for (int i=1;i<=n;i++)
    {
        if (!viz[i])
        {
        dfs(i);
        cc++;
        }
    }
    fout<<cc;
    return 0;
}