Cod sursa(job #1698860)

Utilizator perjulucianPerju Lucian Ionut perjulucian Data 5 mai 2016 16:09:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <iostream>
#include <vector>

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

int N,M;

std::vector <std::vector<int>> adjList;

bool visited[100001];

void read(){

    for(int i = 0 ; i <= N ; ++i){
        adjList.push_back(std::vector<int>());
    }
    int from,to;
    
   
    for(int i = 1 ; i <= M ; ++i){
        f >> from >> to;
        adjList.at(from).push_back(to);
        adjList.at(to).push_back(from);
    }
}

void dfs(int nod){
    visited[nod] = true;
    for(unsigned int i = 0 ; i < adjList.at(nod).size() ; ++i){
        if(!visited[adjList.at(nod).at(i)]){
            dfs(adjList.at(nod).at(i));
        }
    }
}


int main(){
    
    f >> N >> M;

    read();

    int CC = 0;
    for(int i = 1 ; i <= N ; ++i){
        if(!visited[i]){
            dfs(i);
            ++CC;
        }
    }
    g << CC;


    f.close();
    g.close();
    
    return 0;
}