Cod sursa(job #2263211)

Utilizator cristicioteiCiotei Cristian cristiciotei Data 18 octombrie 2018 13:52:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
vector <int> v[200001];
int vazut[100001];
int n, m,x1,x2;
void citire ()
{
    cin>>n>>m;
    for (int i=0 ; i<m ; i++ )
    {
        cin>>x1>>x2;
        v[x1].push_back(x2);
        v[x2].push_back(x1);
    }
}
void afisare ()
{
    for (int i=0 ; i<n ; i++)
    {
        cout<<i<<"=";
        for (int j=0 ; j<v[i].size() ; j++)
            cout<<v[i][j]<<" ";
        cout<<endl;
    }

}
int cont;
void DFS (int nod)
{
        vazut[nod]=1;
        for (int i=0 ; i<v[nod].size();i++)
            if (vazut[v[nod][i]]==0)
                DFS(v[nod][i]);
}

int main()
{
    freopen ("dfs.in","r",stdin);
    freopen ("dfs.out","w",stdout);
    citire ();
    for (int i=1 ; i<=n ; i++)
        if (vazut[i]==0)
    {
        cont++;
        DFS(i);
    }
    cout<<cont;
    return 0;
}