Cod sursa(job #850796)

Utilizator Athena99Anghel Anca Athena99 Data 8 ianuarie 2013 22:52:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cassert>
#include <cstdio>
#include <vector>

const int nmax=100005;
using namespace std;

bool u[nmax];
vector <int> v[nmax];

void dfs(int k)
{
    int i=0;
    u[k]=1;
    for (i=0; i<v[k].size(); ++i)
        if (u[v[k][i]]==0)
            dfs(v[k][i]);
}


int main()
{
    int n=0,m=0,cnt=0,i=0,x=0,y=0;

    assert(freopen("dfs.in","r",stdin));
    assert(freopen("dfs.out","w",stdout));

    assert(scanf("%d%d",&n,&m));

    for (i=0; i<m; ++i)
    {
        assert(scanf("%d%d",&x,&y));
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for (i=1; i<n+1; ++i)
        if (u[i]==0)
        {
            dfs(i);
            ++cnt;
        }

    assert(printf("%d\n",cnt));

    return 0;
}