Cod sursa(job #1123992)

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

using namespace std;

int N, M, rez = 0;

vector<vector<int> > V;

vector<int> VIZ;

void solve(int i)
{

    VIZ[i] = 1;

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

}

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);

    }

    for(int i=1;i<=N;++i)
    {
        if(!VIZ[i])
        {
            solve(i);
            ++rez;
        }

    }
    /*
    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;
}