Cod sursa(job #1651170)

Utilizator azbe11Anonim azbe11 Data 12 martie 2016 15:40:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
using namespace std;

void dfs(const vector<vector<int> > &graph,const int &s,const int &k,vector<int> &visited)
{
    visited[s]=k;
    stack<int> st;
    int elem,i;
    bool found;
    st.push(s);
    while(!st.empty())
    {
        elem=st.top();
        found=false;
        for(i=0;i<graph[elem].size() && !found;i++)
        {
            if(!visited[graph[elem][i]])
                found=true;
        }
        if(found)
        {
            i--;
            st.push(graph[elem][i]);
            visited[graph[elem][i]]=k;
        }
        else st.pop();
    }
}

int main()
{
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    int v,e,nrconex=0,i,aux1,aux2;
    vector<vector<int> > graph;
    vector<int> visited;
    fin>>v>>e;
    graph.resize(v);
    visited.resize(v,0);
    for(i=0;i<e;i++)
    {
        fin>>aux1>>aux2;
        aux1--;
        aux2--;
        graph[aux1].push_back(aux2);
        graph[aux2].push_back(aux1);
    }
    for(i=0;i<v;i++)
    {
        if(!visited[i])
        {
            nrconex++;
            dfs(graph,i,nrconex,visited);
        }
    }
    fout<<nrconex;
    return 0;
}