Cod sursa(job #2594025)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 5 aprilie 2020 11:20:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <vector>

using namespace std;

const int maxn = 100005;
ifstream cin("dfs.in");
ofstream cout("dfs.out");

int N, M;
vector < vector <int> > G;
bool viz[maxn];

void citire()
{
    cin >> N >> M;
    int x, y;

    G.resize(maxn + 5);
    for(int i = 1 ; i <= M ; i++)
        cin >> x >> y, G[x].push_back(y), G[y].push_back(x);

}

void DFS(int poz)
{
    if(viz[poz])
        return;

    viz[poz] = 1;
    for(int i = 0 ; i < G[poz].size() ; i++)
        DFS(G[poz][i]);

}

void rez()
{
    int nr = 0;


    for(int i = 1 ; i <= N ; i++)
        if(!viz[i])
        {
            nr++, DFS(i);

            /*for(int j = 1 ; j <= N ; j++)
                cout << j << ' ' << viz[j] << '\n';
            cout << '\n';*/
        }


    cout << nr;
}

int main()
{
    citire();
    rez();
    return 0;
}