Cod sursa(job #2255034)

Utilizator escapeMCroCoroian Sebastian escapeMCro Data 6 octombrie 2018 12:36:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<vector>
#include<iostream>
#include<fstream>

#define NMAX 100005

using namespace std;

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

vector <int> G[NMAX];
bool viz[NMAX];

//long long A[NMAX][NMAX], viz[NMAX];
long long N,M,aux1,aux2,cnt=0;
bool DFS(int n)
{
    viz[n]=1;
    int nrvecini=G[n].size();
    for(int i=0; i<nrvecini; i++)
    {
        int vecin=G[n][i];
        if(viz[vecin]==0)
            DFS(vecin);

    }
}

int main()
{
    fin>>N>>M;
    for(int i=1; i<=M; i++)
    {
        fin>>aux1>>aux2;

        G[aux1].push_back(aux2);
        G[aux2].push_back(aux1);
    }
    for(int i=1; i<=N; i++)
    {
        if(viz[i]==0)
        {
            DFS(i);
            cnt++;
        }
    }
    fout<<cnt;
}