Cod sursa(job #2438504)

Utilizator Adrian_Popescu311Popescu Adrian Adrian_Popescu311 Data 12 iulie 2019 17:07:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <assert.h>

using namespace std;

ifstream fi("dfs.in");
ofstream fo("dfs.out");

#define dim 100010

vector <long int> G[dim];
int viz[dim];
long int n,m;
long int nr;

void dfs(long int nod)
{
    viz[nod]=1;

    for(long int i=0;i<G[nod].size();i++)
        if(viz[G[nod][i]]==0)
            dfs(G[nod][i]);
}

int main()
{
    fi>>n>>m;

    for(long int i=1;i<=m;i++)
    {
        long int x,y;

        fi>>x>>y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(long int i=1;i<=n;i++)
        if(!viz[i])
            {dfs(i);
            ++nr;}

    fo<<nr;

    return 0;
}