Cod sursa(job #2063407)

Utilizator ruxi.icleanuRuxandra Icleanu ruxi.icleanu Data 11 noiembrie 2017 11:21:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

#define MAXN 100000

vector <int> g[MAXN+1];
char seen[MAXN+1];

void dfs(int node) {
    int i, l;
    seen[node]=1;
    l=g[node].size();
    for(i=0; i<l; i++)
        if(seen[g[node][i]]!=1)
            dfs(g[node][i]);
}

int main()
{
    int n, m, x, y, i, nr;
    FILE *fi, *fo;
    fi = fopen("dfs.in", "r");
    fo = fopen("dfs.out", "w");
    fscanf(fi, "%d%d", &n, &m);
    for(i=0; i<m; i++) {
        fscanf(fi, "%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    nr=0;
    for(i=1; i<=n; i++)
        if(seen[i]==0) {
            dfs(i);
            nr++;
        }
    fprintf(fo, "%d", nr);
    return 0;
}