Cod sursa(job #2557553)

Utilizator richardionelRichard Ionel richardionel Data 25 februarie 2020 21:08:27
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

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

vector <int> muchii [100001];
int n ,m ,cnt = 0;
int vizitat[100001];

void dfs (int nodinceput)
{

    vizitat[nodinceput] = 1;
    for (int i = 0 ;i < muchii[nodinceput].size() ;i++)
    {   int nodprezent = muchii[nodinceput][i];
        if (vizitat[nodprezent] == 0)
            dfs(nodprezent);
    }
}

void read()
{
    int x ,y;
    for (int i = 1 ;i <= m ;i++)
    {
        fin >> x >> y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }
}

int main()
{
    read();
    for (int i = 1 ;i <= n ;i++)
    {
        if (vizitat[i] == 0)
            dfs(i);
            cnt++;
    }
    fout << cnt;
    return 0;
}