Cod sursa(job #2221635)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 15 iulie 2018 10:42:25
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>

using namespace std;

int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    vector<int> edges[100010];
    int n, m;
    scanf("%d", &n);
    scanf("%d", &m);
    for(int i = 0; i < m; ++i)
    {
        int a, b;

        scanf("%d", &a);
        scanf("%d", &b);
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    vector<int> v(n + 1, 0);
    int c = 0;
    for(int i = 0; i < n; ++i)
    {
        if(!v[i])
        {
            stack<int> s;
            s.push(i);
            v[i] = 1;
            while(!s.empty())
            {
                int nod = s.top();
                for(int j = 0; j < edges[nod].size(); ++j)
                {
                    int nod2 = edges[nod][j];
                    if(!v[nod2])
                    {
                        s.push(nod2);
                        v[nod2] = 1;
                    }
                }
                s.pop();
            }
            ++c;
        }
    }

    printf("%d", c);

    return 0;
}