Cod sursa(job #1975338)

Utilizator icansmileSmileSmile icansmile Data 30 aprilie 2017 15:55:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>

#define WHITE 0
#define BLACK 1
#define GREY 2

void dfs();
void explore(int node);

std::vector<std::vector<int>> graph;
std::vector<int> colors;
std::vector<int> distance;

int T = 0;
int number = 0;

int main() {
    int N,M;

    FILE *in = fopen("dfs.in","r");
    FILE *out = fopen("dfs.out","w");

    fscanf(in,"%d",&N);
    fscanf(in,"%d",&M);

    for(int i = 0; i < N; i++) {
        std::vector<int> temp;
        graph.push_back(temp);
        distance.push_back(INT32_MAX);
    }

    for(int i = 0; i < M; i++) {
        int start,end;
        fscanf(in,"%d %d",&start,&end);
        if(start != end) {
            graph[start - 1].push_back(end - 1);
            graph[end  - 1].push_back(start - 1);
        }
    }

    dfs();

    fprintf(out,"%d",number);

    fclose(in);
    fclose(out);
    return 0;
}

void dfs() {
    for(int i = 0; i < graph.size(); i++) {
        colors.push_back(WHITE);
    }
    T = 0;
    for(int i = 0; i < graph.size(); i++) {
        if( colors[i] == WHITE ) {
            explore(i);
            number++;
        }
    }
}

void explore(int node) {
    distance[node] = T++;
    colors[node] = GREY;

    for(int neightbords : graph[node]) {
        if (colors[neightbords] == WHITE) {
            explore(neightbords);
        }
    }

    colors[node] = BLACK;
    T++;
}