Cod sursa(job #2199634)

Utilizator Evrika12Mihnea Rontescu Evrika12 Data 28 aprilie 2018 16:07:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 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 comp,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 dfs (int x)
{
    viz[x]=comp;
    int p=lst[x],y;
    while(p!=0)
    {
        y=vf[p];
        if(!viz[y])
        {
            dfs(y);
        }
        p=urm[p];
    }
}

int main( )
{
    int x,y,i;
    in>>n>>m;
    for(i=0;i<m;i++)
    {
        in>>x>>y;
        adauga(x,y);
        adauga(y,x);
    }
    for(i=1;i<=n;i++)
    {
        if(!viz[i])
        {
            comp++;
            dfs(i);
        }
    }
    out<<comp;
    return 0;
}