Cod sursa(job #2066631)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 15 noiembrie 2017 10:55:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#define DIM 100010
using namespace std;
int f[DIM], L[DIM];
int *v[DIM];
int comp, n, m, i, x, y;
void dfs(int nod) {
    f[nod] = 1;
    for (int i=0;i<L[nod];i++)
        if (f[ v[nod][i] ] == 0)
            dfs(v[nod][i]);
}

int main () {
    ifstream fin ("dfs.in");
    ofstream fout("dfs.out");

    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        f[x]++;
        f[y]++;
    }
    fin.close();
    ifstream fin1("dfs.in");
    fin1>>n>>m;

    for (i=1;i<=n;i++)
        v[i] = new int[f[i]];

    for (int i=1;i<=m;i++) {
        fin1>>x>>y;
        v[x][ L[x]++ ] = y;
        v[y][ L[y]++ ] = x;
    }

    for (i=1;i<=n;i++)
        f[i] = 0;

    for (i=1;i<=n;i++)
        if (f[i] == 0) {
            comp++;
            dfs(i);
        }
    fout<<comp;
    return 0;
}