Pagini recente » Cod sursa (job #219331) | Cod sursa (job #1983838) | Cod sursa (job #1124020) | Cod sursa (job #2544845) | Cod sursa (job #1453576)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
struct Node {
int discoveryTime;
int lowLink;
std::vector<int> neighbors;
bool inStack;
Node() {
discoveryTime = -1;
lowLink = -1;
inStack = false;
}
};
int g_time = 1, g_counter;
std::stack<int> s;
std::vector<std::vector<int> > components;
void tarjan (int index, std::vector<Node>& graph) {
s.push (index);
graph[index].inStack = true;
graph[index].discoveryTime = g_time;
graph[index].lowLink = g_time;
g_time++;
auto neighbors = graph[index].neighbors;
for (int i = 0; i < neighbors.size(); ++i) {
if (graph[neighbors[i]].discoveryTime == -1) {
tarjan (neighbors[i], graph);
graph[index].lowLink = std::min (graph[index].lowLink, graph[neighbors[i]].lowLink);
} else {
if (graph[neighbors[i]].inStack) {
graph[index].lowLink = std::min (graph[index].lowLink, graph[neighbors[i]].discoveryTime);
}
}
}
if (graph[index].lowLink == graph[index].discoveryTime) {
std::vector<int> ctc;
int aux = -1;
g_counter++;
do {
aux = s.top();
ctc.push_back (aux);
s.pop();
graph[aux].inStack = false;
} while (aux != index);
components.push_back (ctc);
}
}
int main() {
std::ifstream fin ("ctc.in");
std::ofstream fout ("ctc.out");
int n, m;
fin >> n >> m;
std::vector<Node> graph (n + 1);
for (int i = 0; i < m; ++i) {
int source, dest;
fin >> source >> dest;
graph[source].neighbors.push_back (dest);
}
for (int i = 1; i <= n; ++i) {
if (graph[i].discoveryTime == -1) {
tarjan (i, graph);
}
}
fout << g_counter << "\n";
// std::cout << "nr comp: " << g_counter << "\n";
// std::cout << "prima: " << components[0].size() << "\na doua: " << components[1].size() << "\n";
for (int i = 0; i < g_counter; ++i) {
// std::cout << "intra i\n";
for (int j = 0; j < components[i].size(); ++j) {
// std::cout << "intra j\n";
fout << components[i][j] << " ";
// std::cout << components[i][j] << " ";
}
fout << "\n";
}
return 0;
}