Cod sursa(job #1198817)

Utilizator japjappedulapPotra Vlad japjappedulap Data 17 iunie 2014 12:00:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
//queue method
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream is ("dfs.in");
ofstream os ("dfs.out");

int N, M, sol;

vector <int> nod[100002];
bool marked[100002];
queue <int> Q;

void Read();
void DFS();

int main()
{
    Read();
    DFS();
    is.close();
    os.close();
}

void Read()
{
    is >> N >> M;
    int a, b;
    for (int i = 0; i < M; ++i)
    {
        is >> a >> b;
        nod[a].push_back(b);
        nod[b].push_back(a);
    }
};

void DFS()
{
    for (int i = 1; i <= N; ++i)
    {
        if (marked[i] == false)
        {
            ++sol;
            Q.push(i);
            for (; !Q.empty(); Q.pop())
            {
                for (int j = 0; j < nod[Q.front()].size(); ++j)
                {
                    if (marked[nod[Q.front()][j]] == 0)
                    {
                        marked[nod[Q.front()][j]] = 1;
                        Q.push(nod[Q.front()][j]);
                    }
                }
            }
        }
    }
    os << sol;
};