Cod sursa(job #867001)

Utilizator razvan.popaPopa Razvan razvan.popa Data 28 ianuarie 2013 23:02:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<iostream>
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#define INF (1 << 30)
#define pb push_back
#define mkp make_pair
#define pii pair<int, int>
#define ll long long
#define nxt (*it)
#define type int
#define FORi(i,a,b)\
   for(int i=a; i<=b; ++i)
#define FORr(g)\
   for(vector<type>::reverse_iterator it=g.rbegin(); it!=g.rend(); ++it)
#define FOR(g)\
   for(vector<type>::iterator it=g.begin(); it!=g.end(); ++it)
#define infile "dfs.in"
#define outfile "dfs.out"
#define nMax 100005
using namespace std;

vector < int > v[nMax];

bitset < nMax > used;

int N, M, nrC;


void read(){
    ifstream f(infile);

    f >> N >> M;

    int x, y;
    while(M--){
        f >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }

    f.close();
}

void dfs(int x){
    stack < int > S;

    S.push(x);
    used[x] = true;
    while(!S.empty()){
        x = S.top();
        S.pop();
        used[x] = true;

        FOR(v[x])
           if(!used[nxt])
              S.push(nxt);
    }
}

void solve(){
    FORi(i,1,N)
       if(!used[i]){
           dfs(i);
           nrC ++;
       }
}

void print(){
    ofstream g(outfile);

    g << nrC << '\n';

    g.close();
}

int main(){
    read();
    solve();
    print();

    return 0;
}