Cod sursa(job #1359386)

Utilizator cristian.enciuCristian Enciu cristian.enciu Data 24 februarie 2015 22:21:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
#include<vector>
#include<stack>

using namespace std;

bool v[1000010];
vector<vector<int> > nodes;
stack<int> st;
int n, m;

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

	scanf("%d%d", &n, &m);

	for(int i = 0 ; i <= n ; ++i) {
		vector<int> x;
		nodes.push_back(x);
	}

	for(int i = 0 ; i < m ; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		nodes[x].push_back(y);
		nodes[y].push_back(x);
	}

	int count = 0;

	for(int i = 1 ; i <= n ; ++i) {
		if(!v[i]) {
			++count;

			st.push(i);

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

				for(int i : nodes[x]) {
					if(!v[i]) {
						st.push(i);
						v[i] = 1;
					}
				}
			}
		}
	}


	printf("%d", count);

	return 0;
}