Cod sursa(job #1244860)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 18 octombrie 2014 12:24:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int N, M;
vector<vector<int>> adj(100001);
vector<bool> marked(100001, false);

void dfs(int source){
	stack<int> st;

	st.push(source);

	while(!st.empty()){
		int node = st.top();
		st.pop();

		for(int i = 0; i < adj[node].size(); i++){
			if(!marked[adj[node][i]]){
				marked[adj[node][i]] = true;
				st.push(adj[node][i]);
			}
		}
	}
}

int main(){
	int from, to, cnt = 0;
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	scanf("%d%d", &N, &M);
	for(int i = 0; i < M; i++){
		scanf("%d%d", &from, &to);
		adj[--from].push_back(--to);
		adj[to].push_back(from);
	}
	for(int i = 0; i < N; i++){
		if(!marked[i]){
			dfs(i);
			cnt ++ ;
		}
	}
	printf("%d\n", cnt);
	return 0;
}