Cod sursa(job #2519012)

Utilizator marinaoprOprea Marina marinaopr Data 6 ianuarie 2020 21:39:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
#include <vector>

using namespace std;

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

vector <vector <int> > vf;

int n,m,i,ok[100005],ans,x,y;

void dfs(int x)
{
    int i;

    ok[x] = 1;
    for(i=0; i<vf[x].size(); ++i)
        if(!ok[vf[x][i]])
            dfs(vf[x][i]);
}

int main()
{
    fscanf(fin, "%d%d", &n,&m);
    vf.resize(n+1);

    for(i=1; i<=m; ++i)
    {
        fscanf(fin, "%d%d", &x,&y);
        vf[x].push_back(y);
        vf[y].push_back(x);
    }

    for(i=1; i<=n; ++i)
        if(!ok[i])
        {
            ++ans;
            dfs(i);
        }

    fprintf(fout, "%d", ans);

    fclose(fin);
    fclose(fout);
    return 0;
}