Pagini recente » Cod sursa (job #742034) | Cod sursa (job #498788) | Cod sursa (job #2357091) | Cod sursa (job #735569) | Cod sursa (job #1993859)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
void visitA(int node, std::vector<std::list<int>> &graph,
std::vector<bool> &check, std::list<int> &myS) {
for (int aux : graph[node]) {
if (!check[aux]) {
check[aux] = true;
visitA(aux, graph, check, myS);
}
}
myS.push_back(node);
}
void visitB(int node, std::vector<std::list<int>> &graph,
std::vector<bool> &check, std::ostream &out) {
out << node << ' ';
for (int aux : graph[node]) {
if (!check[aux]) {
check[aux] = true;
visitB(aux, graph, check, out);
}
}
}
int main() {
std::ifstream fileIn("ctc.in");
std::ofstream fileOut("ctc.out");
int nV, nM;
fileIn >> nV >> nM;
std::vector<std::list<int>> graph(nV + 1);
std::vector<std::list<int>> trans(nV + 1);
int a, b;
for (int i(0); i < nM; i++) {
fileIn >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
std::vector<bool> check(nV + 1, false);
std::list<int> myS;
for (int i(1); i <= nV; i++) {
if (!check[i]) {
check[i] = true;
visitA(i, graph, check, myS);
}
}
check = std::vector<bool>(nV + 1, false);
while (!myS.empty()) {
a = myS.back();
myS.pop_back();
if (!check[a]) {
check[a] = true;
visitB(a, trans, check, fileOut);
fileOut << '\n';
}
}
fileIn.close();
fileOut.close();
return 0;
}