Cod sursa(job #984200)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 13 august 2013 19:33:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>

using namespace std;

#define Nmax 100005

int *G[Nmax];
int degree[Nmax];
int viz[Nmax];

int N, M;

void read()
{
    fstream f;

    f.open( "dfs.in", ios::in );

    f >> N >> M;

    for ( int i = 1, a, b; i <= M; ++i )
    {
        f >> a >> b;

        degree[a]++;;
        degree[b]++;
    }

    f.close();

    f.open( "dfs.in", ios::in );

    f >> N >> M;

    for ( int i = 1; i <= N; degree[i++] = 0 )
            G[i] = new int[degree[i] + 1];

    for ( int i = 1, a, b, c; i <= M; ++i )
    {
        f >> a >> b;

        G[a][ degree[a]++ ] = b;
        G[b][ degree[b]++ ] = a;
    }

    for ( int i = 1; i <= N; i++ )
    {
        G[i][degree[i]] = -1;
        degree[i] = 0;
    }

    f.close();
}

void DFS( int nod )
{
    viz[nod] = 1;

    for ( int *p = G[nod]; *p != -1; p++ )
            if ( !viz[ *p ] )
                    DFS( *p );
}

void solve()
{
    ofstream g("dfs.out");

    int s = 0;

    for ( int i = 1; i <= N; ++i )
            if ( !viz[i] )
            {
                s++;
                DFS( i );
            }

    g << s << "\n";

    g.close();
}

int main()
{
    read();
    solve();

    return 0;
}