Cod sursa(job #2103530)

Utilizator inquisitorAnders inquisitor Data 10 ianuarie 2018 14:14:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <stack>
#include <list>
using namespace std;

int vertices, edges, u, v;
list<int> adj[100001];
bool visited[100001];
int conexParts;

void DFS(int start){
    stack<int> S;
    S.push(start);

    while(!S.empty()){
        int current = S.top(); S.pop();
        if(visited[current] == false){
            visited[current] = true;
            for(list<int> :: iterator it = adj[current].begin(); it != adj[current].end(); it++){
                S.push(*it);
            }
        }
    }
}

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(visited[i] == false){
        conexParts++;
        DFS(i);
    }
}printf("%d", conexParts);

return 0;
}