Cod sursa(job #1168561)

Utilizator pop_bogdanBogdan Pop pop_bogdan Data 8 aprilie 2014 22:56:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

#define MAX 100001

int N, M, Sol, x, y;
vector <int> V[MAX];
bool d[MAX];
queue <int> Q;

void Input();
void DFS();

int main()
{
    Input();
    DFS();

    os << Sol;


    is.close();
    os.close();
}

void Input()
{
    is >> N >> M;
    for ( int i = 1; i <= M; ++i )
    {
        is >> x >> y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
}

void DFS()
{
    for ( int i = 1; i <= N; ++i )
    {
        if ( d[i] == false )
        {
            ++Sol;
            Q.push(i);
            while ( !Q.empty() )
            {
                for ( int j = 0; j < V[Q.front()].size(); ++j )
                {
                    if ( d[V[Q.front()][j]] == 0 )
                    {
                        d[V[Q.front()][j]] = 1;
                        Q.push(V[Q.front()][j]);
                    }

                }
                Q.pop();
            }
        }
    }
}