Pagini recente » Cod sursa (job #2981572) | Cod sursa (job #1649518) | Cod sursa (job #1167851) | Cod sursa (job #580007) | Cod sursa (job #1993866)
#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::list<int> &out) {
out.push_back(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);
std::list<std::list<int>> out;
while (!myS.empty()) {
a = myS.back();
myS.pop_back();
if (!check[a]) {
check[a] = true;
out.push_back(std::list<int>());
visitB(a, trans, check, out.back());
}
}
fileOut << out.size() << '\n';
for (std::list<int> strong : out) {
for (int vertex : strong) {
fileOut << vertex << ' ';
}
fileOut << '\n';
}
fileIn.close();
fileOut.close();
return 0;
}