Cod sursa(job #698915)

Utilizator laurionLaurentiu Ion laurion Data 29 februarie 2012 16:42:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#define nume "dfs"

#include<cstdio>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<string>
#include<sstream>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<set>
#include<stack>
#include<map>
#include<ctime>
#include<list>
#include<algorithm>

using namespace std;

//#define _PARSARE_
#ifdef _PARSARE_
#define DIM 8192
char ax[DIM+16];
int idx;
inline void cit(int &x)
{
    x=0;
    while((ax[idx]<'0' || ax[idx]>'9') && (ax[idx]!='-'))
        if(++idx==DIM)fread(ax, 1, DIM, stdin), idx=0;

    int neg=0;
    if(ax[idx]=='-') {
        neg=1;
        if(++idx==DIM)fread(ax, 1, DIM, stdin),idx=0;
    }

    while(ax[idx]>='0' && ax[idx]<='9') {
        x=x*10+ax[idx]-'0';
        if(++idx==DIM)fread(ax,1, DIM, stdin),idx=0;
    }
    if(neg) x=-x;
}
#else
ifstream fin (nume".in");
#endif //_PARSARE_
ofstream fout(nume".out");
//#ifndef ONLINE_JUDGE
//	freopen("input.txt","r",stdin);
//#endif

#define foreach(V) for(vector<int>::iterator it=V.begin(),stop=V.end();it!=stop;++it)

int n;
int m;
vector<int> G[100000+10];


bool viz[100000+10];
void df(int nod)
{
    viz[nod]=true;
    foreach(G[nod])
        if(!viz[*it])
            df(*it);
}
int main()
{
#ifdef _PARSARE_
    freopen(nume".in","r",stdin);
    cit_uint(n);
#else
    fin>>n>>m;
#endif

    for(int i=0;i<m;++i)
    {
        int x,y;
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
	int sol=0;
    for(int i=1;i<=n;++i)
        if(!viz[i])
            df(i),sol++;
    fout<<sol<<'\n';
    fout.close();
    return 0;
}