Cod sursa(job #2103526)

Utilizator inquisitorAnders inquisitor Data 10 ianuarie 2018 14:06:40
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

int vertices, edges, u, v, conexParts;

vector<int> adj[100001];

bool visited[100001];

void DFS(int start)
{
    stack<int> s;

    s.push(start);

    while(!s.empty())
    {
        int current = s.top(); s.pop();

        if(current[visited] == false)
        {
            for(auto child : adj[current])
            {
                s.push(child);
            }

            current[visited] = true;
        }
    }
}

int main(){

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

    scanf("%d %d", &vertices, &edges);

    for(int i = 1; i <= edges; i++)
    {
        scanf("%d %d", u, v);

        adj[u].push_back(v);

        adj[v].push_back(u);
    }

    for(int i = 1; i <= vertices; i++)
    {
        if(i[visited] == false)
        {
            DFS(i);

            conexParts++;
        }
    }

    printf("%d", conexParts);

    return 0;
}