Cod sursa(job #871819)

Utilizator gherghe94Andrei Gherghelau gherghe94 Data 5 februarie 2013 12:00:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define lim 100002
using namespace std;
vector <int> Graf[lim] ;
bool viz[lim];
int n , m ;
int x , y;
void citire()
{
    freopen("dfs.in","r",stdin);
    scanf("%d%d",&n , &m);
    for(int i = 0 ; i < m ; ++i)
    {
        scanf("%d %d",&x , &y);
        Graf[x].push_back(y);
        Graf[y].push_back(x);
    }
}
void adancime(int i)
{
    viz[i] = true;
    for(unsigned int j = 0 ; j < Graf[i].size() ; ++j)
    {
        if(!viz[Graf[i][j]])
        {
            //viz[i]=true;
            adancime(Graf[i][j]);
        }
    }
}
int nr = 0;
void afisare()
{
    freopen("dfs.out","w",stdout);
    //--nr;
    printf("%d\n" , nr);
}
int main()
{
    citire();

    for(int i = 1 ; i <= n ; ++i)
    {
        if(!viz[i]){
            nr++;
            adancime(i);
        }
    }

    afisare();
    return 0;
}