Cod sursa(job #2217069)

Utilizator razviii237Uzum Razvan razviii237 Data 28 iunie 2018 21:06:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

#define fs fscanf
#define fp fprintf

#define MAXN 100005

using namespace std;

FILE *f, *g;

typedef struct nod
{
    int x;
    nod *a;
} *pNod;
pNod v[MAXN];

void add(pNod &dest, int val)
{
    pNod p;
    p = new nod;
    p -> x = val;
    p -> a = dest;
    dest = p;
}

bool viz[MAXN];
void dfs(int nd)
{
    viz[nd] = true;
    pNod p;
    for(p = v[nd]; p != NULL; p = p -> a)
    {
        if(viz[ p -> x ] == false)
        {
            dfs( p -> x );
        }
    }
}

int n, i, x, y, minim, maxim, cnt, m;
int main()
{
    f = fopen("dfs.in", "r");
    g = fopen("dfs.out", "w");

    fs(f, "%d%d", &m, &n);
    for(i = 1; i <= n; i ++)
    {
        fs(f, "%d%d", &x, &y);
        add(v[x], y);
        add(v[y], x);
    }

    for(i = 1; i <= m; i ++)
    {
        if(viz[i] == false)
        {
            cnt ++;
            dfs(i);
        }
    }

    fp(g, "%d", cnt);

    fclose(f);
    fclose(g);
    return 0;
}