Cod sursa(job #372564)

Utilizator cristiprgPrigoana Cristian cristiprg Data 10 decembrie 2009 20:07:34
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <cstdio>
#include <vector>
using namespace std;
#define DIM 50005
#define pb push_back
int t[2 * DIM], nrc;
int radacina(int x)
{
    while (t[x])
        x = t[x];

    return x;
}

void reuniune(int x, int y)
{
    int ry = radacina(y),
    rx = radacina(x);
    if (rx != ry)
        t[rx] = ry, --nrc;
}

/*
struct nod
{
    int x;
    nod *next;
};
nod *list[DIM];


int n, m, t, v[DIM], ord[DIM];

void DFS(int q)
{

    v[q] = 1;
    nod *tt = list[q];
    while (tt != NULL)
    {
        if (!v[tt -> x])
            DFS(tt->x);

        tt = tt -> next;
    }

    t++;
    ord[t] = q;
}
*/


int main()
{/*
    FILE *f = fopen("sortaret.in", "r");
    fscanf(f, "%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
       list[i] = NULL;

    int x, y;

    for (int i = 1; i <= m; ++i)
    {
        nod *t;
        fscanf(f, "%d%d", &x, &y);
        t = new nod;
        t -> x = y;
        t -> next = list[x];
        list[x] = t;



    }
    for (int i = 1; i <= n; ++i)
        if (!v[i])
            DFS(i);

    fclose(f);
    f = fopen ("sortaret.out", "w");
    for (;t;--t)
        fprintf (f, "%d ", ord[t]);


    for (int i = 1; i <= n; ++i)
    {
        nod *t = list[i];
        while (t != NULL)
            printf ("%d ", t->x), t = t -> next;

        printf ("\n");
    }

    fclose(f);

*/

    FILE *f = fopen("dfs.in", "r");
    int n, m, x, y;
    fscanf(f, "%d%d", &n, &m);
    nrc = n;
    for (;m;--m)
    {
        fscanf(f, "%d%d", &x, &y);

        reuniune(x, y);
    }


    fclose(f);

    f = fopen("dfs.out", "w");
    fprintf(f, "%d\n", nrc);
    fclose(f);


    return 0;
}