Cod sursa(job #2672556)

Utilizator MateGMGozner Mate MateGM Data 14 noiembrie 2020 10:46:50
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

void dfs(int start,int n,vector<bool>&ell,const vector<vector<int> >&adj)
{
    vector<int>index(n+1,0);
    stack<int>st;
    st.push(start);
    ell[start]=true;
    while(!st.empty()){
        int v=st.top();
        int vn=adj[v].size();
        int &iv=index[v];
        for(;iv<vn;iv++){
            int sz=adj[v][iv];
            if(!(ell[sz]))
            {
                ell[sz]=true;
                st.push(sz);
                break;
            }
        }
        if(iv>=vn)
            st.pop();
    }
}

int main()
{
    ifstream be("dfs.in");
    ofstream ki("dfs.out");
    int n,m;
    be>>n>>m;
    vector<vector<int> >adj(n+1);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        be>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    vector<bool>ell(n+1,false);
    int db=0;
    for(int i=1;i<=n;i++)
        if(ell[i]==false)
        {
            db++;
            dfs(i,n,ell,adj);
        }
    ki<<db;
    return 0;
}