Playground
//koristi C++11 - http://mendo.mk/Lecture.do?id=26 #include <iostream> #include <vector> #include <stack> #include <cstring> using namespace std; const int MAX_N = 101; vector<int> G[MAX_N]; int visited[MAX_N]; void DFS(int start) { stack<int> stack; stack.push(start); while(!stack.empty()) { int node = stack.top(); stack.pop(); if (visited[node] == 0) { visited[node] = 1; for (auto next : G[node]) { if (visited[next] == 0) { stack.push(next); } } } } } int main() { int N, E; cout << "Number of countries: " << endl; cin >> N; cout << "Number of connections: " << endl; cin >> E; cout << "Enter the connections, one per line." << endl; for (int i=0; i<E; i++) { int country1, country2; cin >> country1 >> country2; G[country1].push_back(country2); G[country2].push_back(country1); //grafot e nenasocen } int numberOfComponents = 0; memset(visited, 0, sizeof(visited)); for (int i=0; i<N; i++) { if (visited[i] == 0) { numberOfComponents++; DFS(i); } } cout << "Number of components: " << numberOfComponents; return 0; }
Input data
Program output
5 3 0 1 0 2 3 4
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!