Cod sursa(job #2549496)

Utilizator gabbie02Thomits Gabriel gabbie02 Data 17 februarie 2020 18:59:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <list>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");
list<unsigned int> * adjlist;
bool * visited;
unsigned int n;

void rd()
{
    unsigned int i, j;
    fin >> n >> i;
    adjlist = new list<unsigned int>[n + 1];
    visited = new bool[n + 1]();
    while(fin >> i >> j){
        adjlist[i].push_back(j);
        adjlist[j].push_back(i);
    }
}

void dfs(unsigned int node)
{
    visited[node] = true;
    for(list<unsigned int>::iterator it = adjlist[node].begin(); it != adjlist[node].end(); it++){
        if(!visited[*it]){
            dfs(*it);
        }
    }
}

int main()
{
    unsigned int comp = 0;
    rd();
    for(unsigned int i = 1; i <= n; i++){
        if(!visited[i]){
            comp++;
            dfs(i);
        }
    }
    fout << comp;
    return 0;
}