Cod sursa(job #2176182)

Utilizator andrei13Paval Andrei andrei13 Data 16 martie 2018 21:25:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>

using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,nrcomp;
list <int> adj[100100];
bool viz[100100];

void dfs(int v)
{
    int st[100100];
    int vf=1;
    st[1]=v;
    viz[v]=1;
    while(vf)
    {
        int nc=st[vf];
        list <int> :: iterator i;
        i=adj[nc].begin();
        while(i!=adj[nc].end() and viz[*i])
        ++i;
        if(i!=adj[nc].end())
        {
            int u=*i;
            st[++vf]=u;
            viz[u]=1;
        }
        else st[vf--]=0;
    }
}
int main()
{f>>n>>m;
for(int i=1;i<=m;++i)
{
    int a,b;
    f>>a>>b;
    adj[a].push_back(b);
    adj[b].push_back(a);
}
for(int i=1;i<=n;++i)
    if(!viz[i])
{
    nrcomp++;
    dfs(i);
}
g<<nrcomp;

        return 0;
}