Cod sursa(job #1560981)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 3 ianuarie 2016 15:51:40
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <vector>

#include <cstdio>
using namespace std;

const int MAX_N = 100002;

template <class T>
class Pointer {
	public:
		Pointer <T> *next;
		Pointer <T> *prev;
		T value;

		Pointer() {
			next = NULL;
			prev = NULL;
		}
};

template <class T>
class Stack {
	Pointer <T> *lo = new Pointer <T>;
	Pointer <T> *hi = new Pointer <T>;
	T value;

	public:
		Stack() {
			lo->next = hi;
			hi->prev = lo;
		}

		void pushElement(T x) {
			Pointer <T> *p = new Pointer <T>;

			p->value = x;
			p->prev = hi;
			hi->next = p;
			hi = p;
		}

		void popElement() {
			hi = hi->prev;
			delete hi->next;
		}

		T getTop() {
			return hi->value;
		}

		bool isEmpty() {
			return lo == hi;
		}
};


int n, m, ans;
vector <int> v[MAX_N];
bool vis[MAX_N];
Stack <int> st;

int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		int x, y;
		
		scanf("%d %d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}

	for(int i = 1; i <= n; ++i) {
		if(vis[i] == true) {
			continue;
		}

		ans++;
		vis[i] = true;
		st.pushElement(i);
		while(st.isEmpty() == false) {
			int x = st.getTop();
			for(int j = v[x].size() - 1; j >= 0; --j) {
				int y = v[x][j];

				v[x].pop_back();
				
				if(vis[y] == false) {
					st.pushElement(y);
					vis[y] = true;
					break;
				}
			}
			st.popElement();
		}
	}

	printf("%d\n", ans);
	
	return 0;
}