Cod sursa(job #2501952)

Utilizator AndreeaGherghescuAndreea Gherghescu AndreeaGherghescu Data 30 noiembrie 2019 12:09:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N=100001;
const int M=2*N;
int lst[N],vf[2*M],urm[2*M],n,nr;
bool viz[N];

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

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

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