Cod sursa(job #2425685)

Utilizator Marcu314Marcu Ionut Marcu314 Data 24 mai 2019 23:32:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include <vector>
#include <cstdlib>

using namespace std;

vector <vector <int>> g;
bool *vizitat;

void DFS(int nod)
{
    vizitat[nod] = true;
    for(auto x:g[nod])
        if(!vizitat[x])
            DFS(x);
}

int main()
{
    int M,N,sol=0;
    FILE *in=fopen("dfs.in","r"), *out=fopen("dfs.out","w");
    fscanf(in,"%i %i",&N,&M);
    vizitat = (bool*)calloc(N+1,sizeof(bool));
    g = vector<vector<int>>(N+1);
    int a,b;
    for(int x=1;x<=M;x++)
    {
        fscanf(in,"%i %i",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int x=1;x<=N;x++)
        if(!vizitat[x])
        {
            DFS(x);
            sol++;
        }
    fprintf(out,"%i",sol);


    return 0;
}