Cod sursa(job #797260)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 13 octombrie 2012 17:41:49
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#include <vector>

#define NMAX 100001

using namespace std;

FILE *inFile = fopen ("dfs.in", "r");
FILE *outFile = fopen ("dfs.out", "w");

vector <int> G[NMAX];

int n;
int c[NMAX];

void read()
{
    int m;
    int x;
    int y;

    fscanf (inFile, "%d %d\n", &n, &m);

    while (m --)
    {
        fscanf (inFile, "%d %d\n", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void dfs(int v, int nr)
{
    for (unsigned int j = 0; j < G[v].size(); ++ j)
    {
        int aux = G[v][j];

        if (c[aux] == 0)
        {
            c[aux] = nr;
            dfs(aux, nr);
        }
    }
}

int count()
{
    int nr = 0;

    for (int i = 0; i < n; ++ i)
        if (c[i] == 0)
        {
            c[i] = ++ nr;
            dfs(i, nr);
        }

    return nr;
}

int main()
{
    read();
    fprintf (outFile, "%d\n", count());

    return 0;
}