Cod sursa(job #1869863)

Utilizator Coroian_DavidCoroian David Coroian_David Data 6 februarie 2017 11:03:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>

using namespace std;

FILE *f, *g;

int k;

int lst[100001];
int urm[400001];
int nod[400001];

int n, m;

bool viz[100001];

int rez;

void add(int a, int b)
{
    k ++;

    nod[k] = b;
    urm[k] = lst[a];

    lst[a] = k;
}

void readFile()
{
    f = fopen("dfs.in", "r");

    fscanf(f, "%d%d", &n, &m);

    int i;
    int a, b;
    for(i = 1; i <= m; i ++)
    {
        fscanf(f, "%d%d", &a, &b);

        add(a, b);
        add(b, a);
    }

    fclose(f);
}

void dfs(int x)
{
    int p = lst[x];

    viz[x] = 1;

    while(p != 0)
    {
        if(viz[nod[p]] == 0)
            dfs(nod[p]);

        p = urm[p];
    }
}

void solve()
{
    int i;
    for(i = 1; i <= n; i ++)
    {
        if(viz[i] == 0)
        {
            rez ++;

            dfs(i);
        }
    }
}

void printFile()
{
    g = fopen("dfs.out", "w");

    fprintf(g, "%d\n", rez);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}