Cod sursa(job #1375124)

Utilizator stefanlaculeanuLaculeanu Stefan stefanlaculeanu Data 5 martie 2015 12:19:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n, m, nr , lst[100005], urm[200005], vf[200005] ;
bool viz[100005];

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

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

int main()
{
    in>>n>>m;
    int a , b ,cnt=0;
    for(int i=1;i<=m;i++)
    {
        in>>a>>b;
        adauga(a , b);
        adauga(b , a);
    }
    for(int i=1;i<=n;i++)
    {
        if(!viz[i])
        {
            cnt++;
            dfs(i);
        }

    }
    out<<cnt;
    return 0;
}