Cod sursa(job #2372826)

Utilizator iliescu99andreiiliescu andrei iliescu99andrei Data 7 martie 2019 11:16:10
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>

#define NMAX 100000

using namespace std;

int vizitat[NMAX];
vector<int> graf[NMAX];

void dfs(int nod){
    vizitat[nod]=1;
    int lim = graf[nod].size();
    for(int i=0;i<lim;i++)
        if(vizitat[graf[nod][i]]==0)
            dfs(graf[nod][i]);
}



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

    int n,m;
    int comp=0;
    int a,b;
    f>>n>>m;

    for(int i = 1; i <= m; i++) {
        f >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    for(int i=1;i<=n;i++)
    {
        if(vizitat[i]==0)
        {
            dfs(i);
            comp++;
        }
    }

    g<<comp;


    return 0;
}