Cod sursa(job #1592924)

Utilizator casuneanu.andreiCasuneanu Andrei Dan casuneanu.andrei Data 8 februarie 2016 10:05:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
#define DMAX 100008
#define IN "dfs.in"
#define OUT "dfs.out"
#define pb push_back
using namespace std;
ifstream fin(IN);
ofstream fout(OUT);

int n, m;
vector < int > graph[DMAX];
int mark[DMAX], conex;

void read();
void solve();
void dfs(int);

int main(){
    read();
    solve();
    fout <<conex<<'\n';
    fout.close();
    return 0;
}

void dfs(int node){
    mark[node] = 1;

    int dim = graph[node].size(), i;
    for (i = 0; i < dim; ++i)
        if (!mark[ graph[node][i] ])
            dfs(graph[node][i]);
}

void solve(){
    int i;
    for (i = 1; i <= n; ++i)
        if (!mark[i]){
            dfs(i);
            ++conex;
        }
}

void read(){
    fin >>n>>m;

    int i;
    int a, b;
    for (i = 0; i < m; ++i){
        fin >>a>>b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
}