Cod sursa(job #1123934)

Utilizator michael9ufoStanescu Mihai michael9ufo Data 26 februarie 2014 10:43:12
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int N, M, rez = 0;

vector<vector<int> > V;

vector<int> VIZ;

void solve()
{
    for(int i=1;i<=N;++i)
    {
        if(!VIZ[i])
        {
            VIZ[i] = 1;
            for(vector<int>::iterator it=V[i].begin();it!=V[i].end();++it)
                VIZ[*it] = 1;
            ++rez;
        }
    }
}

int main()
{

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

    scanf("%d %d", &N, &M);

    for(int i=0;i<=N;++i)
    {

        V.push_back(vector<int>());
        VIZ.push_back(0);
    }

    for(int i=1;i<=M;++i)
    {
        int X, Y;
        scanf("%d %d", &X, &Y);

        V[X].push_back(Y);
        V[Y].push_back(X);

    }

    solve();

/*
    for(vector<vector<int> >::iterator it=V.begin();it!=V.end();++it)
    {
        for(vector<int>::iterator it2=(*it).begin();it2!=(*it).end();++it2)
            cout<<*it2<<" ";
        cout<<"\n";
    }*/

    cout<<rez<<"\n";
    return 0;
}