Cod sursa(job #796411)

Utilizator gherghe94Andrei Gherghelau gherghe94 Data 11 octombrie 2012 13:50:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <vector>
#define Nmax 100002
using namespace std;
int n,m,nr;
bool viz[Nmax];
vector <int> V[Nmax];
void citire()
{
    freopen( "dfs.in" , "r" , stdin);
    scanf("%d %d" , &n , &m);
    for(int i = 0 ; i<m; ++i)
    {
        int x, y;
        scanf("%d %d",&x,&y);
        V[x].push_back(y);
        V[y].push_back(x);
    }
}
void deep(int i)
{
    viz[i] = true;
    for(int p = 0 ; p < V[i].size(); p++)
    {
        if(!viz[V[i][p]])
        {
            viz[V[i][p]] = true;
            deep(V[i][p]);
        }
    }
}
void parcurgere()
{
    for(int i = 1 ; i <= n ; i++)
    {
        if(viz[i] == false)
        {
            nr++;
            deep(i);
        }
    }
}
int main()
{
    freopen("dfs.out", "w" ,stdout);
    citire();
    parcurgere();
    printf("%d\n",nr);
    return 0;
}