Pagini recente » Cod sursa (job #1600730) | Cod sursa (job #995427) | Cod sursa (job #1397534) | Cod sursa (job #184252) | Cod sursa (job #2888219)
#include <vector>
#include <string>
#include <fstream>
using std::vector;
using std::string;
using std::ifstream;
using std::ofstream;
class TareConexe {
private:
int n, m;
string input_file, output_file;
vector<int>* graf;
//vector<int>* graft;
vector<bool> viz;
vector<int> topo;
vector<vector<int>> result;
void read() {
ifstream in(input_file);
in >> n >> m;
graf = new vector<int>[n + 1];
//graft = new vector<int>[n + 1];
viz.resize(n + 1, false);
int x, y;
for (int i = 1; i <= m; ++i) {
in >> x >> y;
graf[x].push_back(y);
//graft[y].push_back(x);
}
in.close();
}
void dfs(int node) {
viz[node] = true;
for (auto vecin : graf[node]) {
if (!viz[vecin]) {
dfs(vecin);
}
}
topo.push_back(node);
}
//void dfst(int node, vector<int>& componenta) {
// componenta.push_back(node);
// viz[node] = false;
// for (auto vecin : graft[node]) {
// if (viz[vecin]) {
// dfst(vecin, componenta);
// }
// }
//}
void solve() {
read();
for (int i = 1; i <= n; ++i) {
if (!viz[i]) {
dfs(i);
}
}
//for (vector<int>::reverse_iterator it = topo.rbegin(); it != topo.rend(); ++it) {
// if (viz[*it]) {
// vector<int> componenta;
// dfst(*it, componenta);
// result.push_back(componenta);
// }
//}
}
public:
TareConexe(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }, topo(), result(){};
void print() {
solve();
ofstream out(output_file);
//out << result.size() << '\n';
//for (auto componenta : result) {
// for (auto node : componenta) {
// out << node << " ";
// }
// out << '\n';
//}
for (vector<int>::reverse_iterator it = topo.rbegin(); it != topo.rend(); ++it) {
out << *it << " ";
}
out.close();
}
~TareConexe() {
delete[] graf;
//delete[] graft;
}
};
int main() {
TareConexe t = TareConexe("sortare.in", "sortare.out");
t.print();
return 0;
}