Cod sursa(job #1651894)

Utilizator robert.iacobIacob Robert robert.iacob Data 14 martie 2016 09:17:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdio>
#include <stack>
#define DimMax 100100

using namespace std;

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

int n,m;
vector <bool> viz;
vector < vector<int> > L;


int Componente_Conexe(int noduri);
int DFS(int k);
void Citire();
void DFS_it(int k);

void Citire()
{
    int x,y,i;
    fin>>n>>m;
    L.resize(n);
    viz.resize(n,false);
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        x--;
        y--;
        L[x].push_back(y);
        L[y].push_back(x);
        ///cout<<x<<" "<<y<<"\n";
    }
    ///cout<<n<<"dfgfe"<<m<<"\n";
}

int Componente_Conexe(int noduri)
{
    int i,cnt=0;
    for(i=0;i<noduri;i++)
        if(viz[i]==false)
        {
            DFS_it(i);
            cnt++;
        }
    return cnt;
}

int DFS(int k)
{
    int i;
    viz[k]=true;
    for(i=0;i<L[k].size();i++)
    {
        if(viz[L[k][i]]==false)
        {
            viz[L[k][i]]=true;
            DFS(i);
        }
    }
}

void DFS_it(int k) {
    if (k  < 0 || k > n - 1) {
            return;
    }

    stack<int> s;
    int i;

    s.push(k);
    viz[k] = true;

    while (!s.empty()) {
        int element = s.top();
        bool found = false;

        for (i = 0; i < L[element].size() && !found; i++) {
            if (!viz[L[element][i]]) {
                found = true;
            }
        }
        if (found) {
            i--;
            s.push(L[element][i]);
            viz[L[element][i]] = true;
        } else {
            s.pop();
        }
    }
}


int main()
{
    Citire();
    fout<<Componente_Conexe(n);
    return 0;
}