Cod sursa(job #2238003)

Utilizator parsulPaul Cristian Banu-Taran parsul Data 4 septembrie 2018 11:02:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<iostream>
#include<fstream>
#include<vector>
#define NMAX 100010
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int N,M,X,Y,conex=0;
bool viz[NMAX];
vector<int>graph[NMAX];
void scan()
{
    in>>N>>M;
    for(int i=0;i<M;i++)
    {
        in>>X>>Y;
        graph[X].push_back(Y);
        graph[Y].push_back(X);
    }
    for(int i=1;i<=N;i++)
        viz[i]=0;
}
void dfs(int nodplecare)
{
    viz[nodplecare]=1;
    for(int i=0;i<graph[nodplecare].size();i++)
        if(!viz[graph[nodplecare][i]])
            dfs(graph[nodplecare][i]);
}
void con()
{
    for(int i=1;i<=N;i++)
        if(!viz[i])
    {
        conex++;
        dfs(i);
    }
}
int main()
{
    scan();
    con();
    out<<conex;
}