Cod sursa(job #700030)

Utilizator joRicelAvadanei Danut joRicel Data 29 februarie 2012 22:57:55
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <vector>
#define Nmax 100001
using namespace std;

int N,M,x,y,Viz[Nmax],nr,dfs(int);
void _read(),_parcurgere();

vector <int> G[Nmax];
int main()
{
    _read();
    _parcurgere();
    printf("%d",nr);
    return 0;
}
void _read()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&N,&M);
    for(int i = 1;i <= M;i++)
    {
        scanf("%d %d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
void _parcurgere()
{
    for(int i = 1;i <= N;i++)
    {
        if(Viz[i] == 0)
        {
            nr++;
            dfs(i);
        }
    }
}
int dfs(int nod)
{
    int i;
    if(Viz[nod])
        return 0;
    Viz[nod] = nr;
    for(i = 0; i <= G[nod].size();i++)
        dfs(G[nod][i]);
    return 0;
}