Cod sursa(job #953063)

Utilizator alexandru93moraru alexandru sebastian alexandru93 Data 24 mai 2013 18:39:00
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<fstream>
#include<stack>
#include<vector>
using namespace std;

int N,M;
vector<int> V[100000];
vector<int> Sel;
stack<bool> S;

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

void Read()
{
    f>>N>>M;
    Sel.resize(N+1);
    for(int i=0;i<M;i++)
    {
        int x,y;
        f>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
}

void DFS(int nod)
{
    S.push(nod);
    Sel[nod]=true;
    while(!S.empty())
    {
        nod=S.top();
        S.pop();
        for(vector<int>::iterator it=V[nod].begin();it!=V[nod].end();it++)
            if(!Sel[*it])
            {
                Sel[*it]=true;
                S.push(*it);
            }
    }
}

int main()
{
    int count=0;
    Read();
    for(int i=1;i<=N;i++)
        if(!Sel[i])
            DFS(1),count++;
    g<<count<<'\n';
    return 0;
}