Cod sursa(job #2388102)

Utilizator alex12_roGuster Alexandru alex12_ro Data 25 martie 2019 17:44:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX=100001;
const int MMAX=200001;
int lst[NMAX], vf[2*MMAX], urm[2*MMAX];
bool viz[NMAX];
int n, m, nr;

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



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


int main()
{
    int i,x,y,nr=0;
    f>>n>>m;

    while(f>>x>>y)
    {
        adauga(x, y);
        adauga(y, x);
    }

    for(i=1; i<=n; i++)

        if(!viz[i])
        {
            nr++;
            dfs(i);
        }
    g << nr;
    return 0;

}