Cod sursa(job #2325658)

Utilizator andrei13Paval Andrei andrei13 Data 22 ianuarie 2019 20:24:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <list>

using namespace std;

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

int m,n,nr;
list <int> adj[100001];
bool conexat[100001];
int stiva[100001];

void dfs(int start)
{
    int vf=1;
    stiva[vf]=start;
    conexat[start]=true;

    while(vf)
    {
        int nc=stiva[vf];
        bool ok=false;
        int nod;
        list <int> :: iterator it;
        for(it=adj[nc].begin();it!=adj[nc].end() and !ok;++it)
        {
            nod=*it;
            if(!conexat[nod])
                ok=true;
        }
        if(ok)
        {
            stiva[++vf]=nod;
            conexat[nod]=true;
        }
        else --vf;
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        f>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
        if(!conexat[i])
    {
        ++nr;
        dfs(i);
    }
    g<<nr;

   return 0;
}