Cod sursa(job #1470115)

Utilizator roxannemafteiuMafteiu-Scai Roxana roxannemafteiu Data 10 august 2015 13:44:40
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <vector>

#define NMAX 100000

FILE *in, *out;

using namespace std;

int N, M, a, b, conexe;
vector <int> graf[NMAX];
bool vizitat[NMAX];

void citire ()
{
    in=fopen("dfs.in", "rt");


    fscanf(in, "%d%d", &N, &M);
    for (int i = 1; i <= M; i++)
    {
        fscanf(in, "%d%d", &a, &b);
        graf[a].push_back(b);
        graf[b].push_back(a);
        //printf(out, "a: %d si b: %d\n", a, b);
    }

    fclose(in);
}

void DFS( int nod)
{
    vizitat[nod]=true;
    int l = graf[nod].size();
    for(int j = 0; j < l; j++)
    {
        int fiu = graf[nod][j];
        if(vizitat[fiu]==false)
            DFS(fiu);
    }}
void afisare ()
{
    out=fopen("dfs.out", "wt");
    for( int i = 1; i <= N; i++)
        if(!vizitat[i])
        {
            conexe++;
            DFS(i);
        }
       /* int l = graf[i].size();
        fprintf(out, "l: %d si %d: ", l, i);

        for( int j = 0; j < l; j++)
        {
            fprintf(out, "%d ", graf[i][j]);
        }

        fprintf(out, "\n");*/

    fprintf(out, "%d", conexe);
    fclose(out);
}

int main()
{
    citire();
    afisare();
    return 0;
}