Cod sursa(job #2199630)

Utilizator Evrika12Mihnea Rontescu Evrika12 Data 28 aprilie 2018 15:54:43
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("dfs.in");
ofstream out ("dfs.out");
const int N = 100001;
const int M = 200001;
int i,n,m,nr=0,lst[N],vf[2*M],urm[2*M],viz[N];
void adauga (int x,int y)
{
    vf[++nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
}
void citire ( )
{
    in>>n>>m;
    int x,y;
    for(int i=0;i<m;i++)
    {
        in>>x>>y;
        adauga(x,y);
        adauga(y,x);
    }
}
bool dfs (int x)
{
    viz[x]=true;
    int p=lst[x],y;
    while(p!=0)
    {
        y=vf[p];
        if(!viz[y])
        {
            dfs(y);
        }
        p=urm[p];
    }
    return true;
}
int main( )
{

    int x,y,r;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y;
        adauga(x,y);
        adauga(y,x);
    }
    r=0;
    for(i=1;i<=n;i++)
    {
        if(dfs(y))
        {
            r++;
        }
    }
    out<<r;
    return 0;
}