Cod sursa(job #1169596)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 11 aprilie 2014 18:23:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>

#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#if __cplusplus > 199711L
#include <unordered_map>
#include <unordered_set>
#endif

#include <cmath>
#include <cstring>
#include <cstdlib>

using namespace std;

int N, M;
vector<int> Graph[100010];
queue<int> Q;
bitset<100010> witness;

int main()
{
    int i, j, x, y, rez = 0, node;
    vector<int>::iterator it;

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

	fin >> N >> M;

	for (i = 0; i < M; ++i)
    {
        fin >> x >> y;
        Graph[x].push_back(y);
        Graph[y].push_back(x);
    }

    for (i = 1; i <= N; ++i)
    {
        if (!witness[i])
        {
            ++rez;
            witness[i] = true;
            Q.push(i);

            while(!Q.empty())
            {
                node = Q.front();
                Q.pop();

                for (it = Graph[node].begin(); it != Graph[node].end(); ++it)
                {
                    if (!witness[*it])
                    {
                        witness[*it] = true;
                        Q.push(*it);
                    }
                }
            }
        }
    }

    fout << rez << '\n';
	fout.close();
    return 0;
}