Cod sursa(job #2007248)

Utilizator epermesterNagy Edward epermester Data 2 august 2017 12:51:09
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<stack>
#include<vector>
using namespace std;

struct csucsok {
	vector<int> szomszedok;
	bool visited = false;
};

int main() {
	ifstream in("dfs.in");
	int N, M;
	in >> N >> M;
	csucsok* csucs = new csucsok[N];
	for (;M;--M) {
		int honnan, hova;
		in >> honnan >> hova;
		csucs[honnan - 1].szomszedok.push_back(hova - 1);
		csucs[hova - 1].szomszedok.push_back(honnan - 1);
	}

	stack<int> s;
	int result = 0;
	for (int i = 0; i < N; ++i)
	{
		if (!csucs[i].visited) {
			s.push(i);
			while (!s.empty()) {
				int jelenlegi = s.top();
				s.pop();
				for (vector<int>::iterator it = csucs[i].szomszedok.begin(); it != csucs[i].szomszedok.end(); it++) {
					if (!csucs[*it].visited) {
						s.push(*it);
						csucs[*it].visited = true;
					}
				}
			}
			result++;
		}
	}
	
	ofstream out("dfs.out");
	out << result;
}