Cod sursa(job #2801402)

Utilizator Ricardo14Olaru Ricardo Ricardo14 Data 16 noiembrie 2021 10:17:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
#include <stdio.h>

using namespace std;

int viz[100000];
vector <int> v[100000];
int h;

void dfs(int varf)
{
    viz[varf]=1;

        for(int i=0;i<v[varf].size();i++)
        {
           if(!viz[v[varf][i]])
            {
                dfs(v[varf][i]);
            }
        }
}
int main()
{
    FILE *fin, *fout;
    int cnt=0,a,n,m,b;

    fin = fopen("dfs.in", "r");
    fscanf(fin, "%d%d", &n, &m);

    for(int i=0;i<m;i++)
    {
        fscanf(fin, "%d%d", &a, &b);
        v[a - 1].push_back(b - 1);
        v[b - 1].push_back(a - 1);
    }
    fclose(fin);

    for(int i=0;i<n;i++)
    {
        if(!viz[i])
        {
            cnt++;
            dfs(i);
        }
    }
    fout = fopen("dfs.out", "w");
    fprintf(fout, "%d", cnt);
    fclose(fout);
    return 0;
}