Cod sursa(job #2666455)

Utilizator DariaCretuCretu Daria Stefana DariaCretu Data 1 noiembrie 2020 21:51:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int N, M, i, X, Y, viz[100001], nr = 0;

vector <int> muchii[100001];

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

void DFS( int nod )
{
    viz[nod] = 1;
    for ( int j = 0; j < muchii[nod].size(); j++ )
        if ( viz[muchii[nod][j]] == 0 )
            DFS(muchii[nod][j]);

}


void citire()
{
    f >> N >> M;
    for ( i = 1; i <= M; i++)
        {
            f >> X >> Y;
            muchii[X].push_back(Y);
            muchii[Y].push_back(X);
        }
}


int main()
{
    citire();

    for ( i = 1; i <= N; i++)
        if ( viz[i] == 0 )
            { nr++; DFS(i);  }
    g << nr;
    return 0;
}