Pagini recente » Cod sursa (job #813174) | Istoria paginii aplicatii-ale-cautarii-binare | Cod sursa (job #1156019) | Cod sursa (job #911845) | Cod sursa (job #2197028)
#include <fstream>
#include <stack>
#include <vector>
int main() {
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
unsigned n, m;
in >> n >> m;
std::vector<std::vector<unsigned>> graph = std::vector<std::vector<unsigned>>();
graph.reserve(n);
std::vector<std::vector<unsigned>> tgraph = std::vector<std::vector<unsigned>>();
tgraph.reserve(n);
for (unsigned i = 0; i < n; i++) {
graph.push_back(std::vector<unsigned>());
tgraph.push_back(std::vector<unsigned>());
}
for (unsigned i = 0; i < m; i++) {
unsigned from, to;
in >> from >> to;
graph[from - 1].push_back(to);
tgraph[to - 1].push_back(from);
}
std::stack<unsigned> s = std::stack<unsigned>();
std::vector<bool> initialVisited = std::vector<bool>();
initialVisited.reserve(n);
for (unsigned i = 0; i < n; i++) initialVisited.push_back(false);
unsigned currentUnvisited = 1;
unsigned numVisited = 0;
std::stack<unsigned> firstDFSStack = std::stack<unsigned>();
while (numVisited < n) {
firstDFSStack.push(currentUnvisited);
initialVisited[currentUnvisited - 1] = true;
do { currentUnvisited++; } while (initialVisited[currentUnvisited - 1] && currentUnvisited < n);
numVisited++;
while (!firstDFSStack.empty()) {
unsigned current = firstDFSStack.top();
bool hasNeighbors = false;
for (unsigned v : graph[current - 1]) {
if (!initialVisited[v - 1]) {
if (v == currentUnvisited) {
do { currentUnvisited++; } while (initialVisited[currentUnvisited - 1] && currentUnvisited < n);
}
hasNeighbors = true;
firstDFSStack.push(v);
initialVisited[v - 1] = true;
numVisited++;
break;
}
}
if (!hasNeighbors) {
s.push(firstDFSStack.top());
firstDFSStack.pop();
}
}
}
std::vector<std::vector<unsigned>> components = std::vector<std::vector<unsigned>>();
std::vector<bool> visited = std::vector<bool>();
visited.reserve(n);
for (unsigned i = 0; i < n; i++) visited.push_back(false);
while (!s.empty()) {
unsigned current = s.top();
if (!visited[current - 1]) {
components.push_back(std::vector<unsigned>());
visited[current - 1] = true;
std::stack<unsigned> dfsStack = std::stack<unsigned>();
dfsStack.push(current);
while (!dfsStack.empty()) {
unsigned curr = dfsStack.top();
bool hasNeighbors = false;
for (unsigned v : tgraph[curr - 1]) {
if (!visited[v - 1]) {
visited[v - 1] = true;
dfsStack.push(v);
hasNeighbors = true;
break;
}
}
if (!hasNeighbors) {
dfsStack.pop();
components[components.size() - 1].push_back(curr);
}
}
}
s.pop();
}
out << components.size() << "\n";
for (auto c : components) {
for (unsigned v : c) {
out << v << " ";
}
out << "\n";
}
return 0;
}