Cod sursa(job #1621035)

Utilizator ajeccAjechiloae Eugen ajecc Data 29 februarie 2016 15:50:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <utility>
#include <unordered_map>
#include <algorithm>
#include <iomanip>
#define for0(i,n) for(int i=0; i<n; i++)
#define for1(i,n) for(int i=1; i<=n; i++)
#define pb push_back
#define mp make_pair
#define ALL(v) v.begin(), v.end()
#define V vector<int>
#define VP vector<pair<int, int> >
#define clr(A,x) memset(A, x, sizeof(A))
#define cpy(A,B) memcpy(A, B, sizeof(B))
#define g(s) getline(fin, s)
#define FASTIO ios_base::sync_with_stdio(0)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MAX=100005;
const ull MOD=100003;
const int NR_CIFRE=100005;
/*template <typename T>
string to_string(const T& n){
    ostringstream os;
    os << n;
    return os.str();
}
*/
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n, m;

vector<vector<int> > v(100001);
queue<int> coada;
bool b[100001];

int main()
{
    int sol=0;
    fin>>n>>m;

    for1(i, m)
    {
        int x, y;
        fin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    for1(i, n)
    {
        if(!b[i])
        {
            sol++;

            b[i]=1;
            for(auto k: v[i])
            {
                b[k]=1;
                coada.push(k);
            }

            while(!coada.empty())
            {
                for(auto k: v[coada.front()])
                {
                    if(!b[k])
                    {
                        b[k]=1;
                        coada.push(k);
                    }
                }
                coada.pop();
            }
        }

    }
    fout<<sol;


    return 0;
}