Cod sursa(job #1400907)

Utilizator MateiTMatei Tita MateiT Data 25 martie 2015 15:37:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

int n,v,m,i,j,a,b,p,nrcomp;
bool viz[100001];
int lst[100001],vf[200002],urm[200001];


void adauga(int x,int y)
{
    m++;
    vf[m]=y;
    urm[m]=lst[x];
    lst[x]=m;
}

void dfs(int x)
{
    int y,p;
    viz[x]=true;
    p=lst[x];
    while(p!=0)
    {
        y=vf[p];
        if(!viz[y])
            dfs(y);
        p=urm[p];
    }
}

int main()
{
    in>>n>>v;
    for(i=1; i<=v; i++)
    {
        in>>a>>b;
        adauga(a,b);
        adauga(b,a);
    }
    for(i=1; i<=n; i++)
        if(viz[i]==0)
        {
            nrcomp++;
            dfs(i);
        }
    out<<nrcomp;
    return 0;
}