Cod sursa(job #1906074)

Utilizator 1475369147896537415369Andrei Udriste 1475369147896537415369 Data 6 martie 2017 12:13:08
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, x, y;
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();
        for(list<int> :: iterator it = adj[current].begin(); it != adj[current].end(); it++){
            if(visited[*it] == false){
                visited[*it] = true;
                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", &x, &y);
    adj[x].push_back(y);
    adj[y].push_back(x);
}
for(int i = 1; i <= vertices; i++){
    if(visited[i] == false){
        conexParts++;
        DFS(i);
    }
}printf("%d", conexParts);

return 0;
}