Cod sursa(job #2203954)

Utilizator caiaandrei14Caia Andrei caiaandrei14 Data 13 mai 2018 20:56:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <vector>

using namespace std;

vector < vector <int> > adia;
vector <int> parinte;
vector <char> culori;
int n, m, nrc;

void citire();
void initializare(int val);
void dfs();
void dfs_viz(int s);

int main(){

    citire();
    dfs();

    return 0;
}

void initializare(int val){
    adia.resize(val + 10);
    culori.resize(val + 10);
    parinte.resize(val + 10);
    for(int i = 1; i <= val; i++)
        adia[i].push_back(0);
}

void citire(){
    FILE* f = fopen("dfs.in", "r");
    fscanf(f, "%d%d", &n, &m);
    initializare(n);
    int x, y;
    for(int i = 0; i < m; i++){
        fscanf(f, "%d%d", &x, &y);
        adia[x][0]++;
        adia[x].push_back(y);
        adia[y][0]++;
        adia[y].push_back(x);
    }
    fclose(f);
}

void dfs(){
    for(int i = 1; i <= n; i++){
        culori[i] = 'a';
        parinte[i] = 0;
    }
    for(int i = 1; i <= n; i++){
        if(culori[i] == 'a'){
            nrc++;
            dfs_viz(i);
        }
    }
    FILE* f = fopen("dfs.out", "w");
    fprintf(f, "%d", nrc);
    fclose(f);
}

void dfs_viz(int s){

    culori[s] = 'g';
    for(int i = 1; i <= adia[s][0]; i++)
        if(culori[adia[s][i]] == 'a'){
            parinte[adia[s][i]] = s;
            dfs_viz(adia[s][i]);
        }
    culori[s] = 'n';
}