Cod sursa(job #2262067)

Utilizator FlaviusFeteanFetean Flavius FlaviusFetean Data 16 octombrie 2018 22:26:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <list>

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

bool conex[100005];

int main()
{
    int n, m, i, ct = 0, x, y;
    list<int> s, l[100005];

    fin >> n >> m;

    for(i = 1; i <= m; i++){
        fin >> x >> y;l[x].push_back(y);
        l[y].push_back(x);
    }

    for(i = 1; i <= n; i++){
        if(conex[i]) continue;

        s.push_back(i); ct++;
        while(!s.empty()){
            x = s.back(); s.pop_back();
            while(!l[x].empty()){
                y = l[x].front();l[x].pop_front();
                conex[y] = 1; s.push_back(y);
            }
        }
    }

    fout << ct;

    return 0;
}