Cod sursa(job #977158)

Utilizator Ionut228Ionut Calofir Ionut228 Data 24 iulie 2013 22:43:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

int N, M;
int sol;
stack<int> ST;
vector<int> V[100001];
bool viz[100001];

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

int main()
{
    fin >> N >> M;
    for (int i = 1, nod1, nod2; i <= M; ++i)
    {
        fin >> nod1 >> nod2;
        V[nod1].push_back(nod2);
        V[nod2].push_back(nod1);
    }

    for (int i = 1; i <= N; ++i)
    {
        if (!viz[i])
        {
            ++sol;
            viz[i] = true;
            ST.push(i);
            DF(i);
        }
    }

    fout << sol;

    fin.close();
    fout.close();
    return 0;
}