Cod sursa(job #1636651)

Utilizator vlad.dumitracheDumitrache Vlad vlad.dumitrache Data 7 martie 2016 11:22:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>

using namespace std;

vector < vector <int> >graph;
vector < bool >visited;
int n,m;
int counter=0;

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

void dfs(int node)
{
    if(node<0||node>n-1)
        return;
    stack <int> a;
    int element,i;
    bool found;
    a.push(node);
    visited[node]=true;
    while(!a.empty())
    {
        element=a.top();
        found=false;
        for(i=0;i<graph[element].size() && !found; i++)
            if(!visited[graph[element][i]])
                found=true;
        if(found)
        {
            i--;
            a.push(graph[element][i]);
            visited[graph[element][i]]=true;
        }
        else
            a.pop();
    }
}

int main()
{
    f>>n>>m; //n elemente/m muchii;
    graph.resize(n);
    int x,y;
    for(int i=0;i<m;i++)
    {
        f>>x>>y;
        x--;y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    visited.resize(n,false);
    for(int i=0;i<n;i++)
        if(!visited[i])
        {
            dfs(i);
            counter++;
        }
    g<<counter<<" ";
    return 0;
}