Cod sursa(job #2358874)

Utilizator Earthequak3Mihalcea Cosmin-George Earthequak3 Data 28 februarie 2019 13:49:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <vector>
#include <fstream>
#define MAXN 100006

using namespace std;

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

vector<int> graph[MAXN];

int viz[MAXN];

void DFS(int n)
{
    viz[n] = 1;
    int limit = graph[n].size();
    for(int i = 0; i < limit; i++)
    {
        int vecin = graph[n][i];
        if(!viz[vecin])
            DFS(vecin);
    }
}

int main()
{

    int k = 0;
    int N,M,a,b;
    f>>N>>M;
    for(int i = 0; i < M; i++ ){
        f>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i = 1;i<=N;i++)
    if(!viz[i]){
        DFS(i);
        k++;

    }
    g<<k;

        return 0;
}