Cod sursa(job #1424240)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 23 aprilie 2015 19:25:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>

#define ull unsigned long long
#define ll long long
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int N,M,conex;
vector<int> v[100010];
bitset<100010> verif;

void depth(int);

int main()
{
    f>>N>>M;
    FOR (i,1,M)
    {
        int x,y;
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    FOR (i,1,N)
    {
        if (!verif[i])
        {
            ++conex;
            depth(i);
        }
    }
    g<<conex;
    f.close();g.close();
    return 0;
}

void depth(int x)
{
    verif[x]=1;
    vector<int>::iterator it;
    for (it=v[x].begin();it<v[x].end();++it)
    {
        if (!verif[*it])
            depth(*it);
    }
}