Cod sursa(job #2544517)

Utilizator Vaida_Radu_AndreiVaida Radu Andrei Vaida_Radu_Andrei Data 12 februarie 2020 10:29:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <vector>
#define VerticesMax 101024

using namespace std;

vector <int> Graph[VerticesMax];
int Vertices,Viz[VerticesMax];

void read() {
    int Edges,I,V1,V2;
    scanf("%d%d",&Vertices,&Edges);
    for(I=0;I<Edges;++I) {
        scanf("%d%d",&V1,&V2);
        --V1;
        --V2;
        Graph[V1].push_back(V2);
        Graph[V2].push_back(V1);
    }
}

void dfs(int Pos) {
    for(auto I:Graph[Pos]) {
        if(!Viz[I]) {
            ++Viz[I];
            dfs(I);
        }
    }
}

void findConexesNr() {
    int Sol,I;
    for(Sol=0,I=0;I<Vertices;++I) {
        if(!Viz[I]) {
            ++Sol;
            ++Viz[I];
            dfs(I);
        }
    }
    printf("%d",Sol);
}

int main() {
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    read();
    findConexesNr();
    return 0;
}