Cod sursa(job #2609916)

Utilizator mzzmaraMara-Ioana Nicolae mzzmara Data 3 mai 2020 19:54:05
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h> 

using namespace std;

const int kNmax = 100005;

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	int m;
	vector<int> adj[kNmax];

	void read_input() {
		ifstream fin("dfs.in");
		fin >> n >> m;
		for (int i = 1, x, y; i <= m; i++) {
			fin >> x >> y;
			adj[x].push_back(y);
		}
		fin.close();
	}

	std::vector<int> get_result() {
        std::vector<int> topologicalSort;
        std::stack<int> nodeStack; 
        std::vector<bool> visited(n + 1, false); 

        for (int i = 1; i <= n; i++) {
          	if (visited[i] == false) {
            	dfsHelper(i, visited, nodeStack);
			}
		}	

        while (nodeStack.size()) {  
            topologicalSort.push_back(nodeStack.top());
            nodeStack.pop();
        }
        return topologicalSort;
    }

    void dfsHelper(int node, std::vector<bool> &visited, std::stack<int> &nodeStack) { 
        visited[node] = true;
        for (int i = 0; i < adj[node].size(); i++) { 
            if (!visited[adj[node][i]]) { 
                dfsHelper(adj[node][i], visited, nodeStack);
            }
        }
        nodeStack.push(node);
    }

	void print_output(vector<int> result) {
		ofstream fout("dfs.out");
		for (int i = 0; i < int(result.size()); i++) {
			fout << result[i] << ' ';
		}
		fout << '\n';
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}