Pagini recente » Cod sursa (job #2697170) | Cod sursa (job #2689818) | Cod sursa (job #1244387) | Cod sursa (job #2562042) | Cod sursa (job #1743357)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
#define MAXN 100005
vector <int> graph[MAXN];
vector<int> new_component, dfs_time, lowlink, in_stack;
vector <vector<int> > components;
stack <int> Stack;
int dfs_time_node_index, nodes_count;
int min (int a, int b) {
if (a < b) {
return a;
}
return b;
}
void read_data() {
ifstream in("ctc.in");
int edges_count;
int node1;
int node2;
in >> nodes_count;
in >> edges_count;
for (; edges_count > 0; -- edges_count) {
in >> node1;
in >> node2;
graph[node1 - 1].push_back(node2 - 1);
}
}
void print_data() {
ofstream out("ctc.out");
out << components.size() << "\n";
for (size_t i = 0; i < components.size(); ++ i) {
for (size_t j = 0; j < components[i].size(); ++ j) {
out << components[i][j] + 1 << " ";
}
out << "\n";
}
}
void recursive_tarjan(int n)
{
dfs_time[n] = lowlink[n] = dfs_time_node_index;
dfs_time_node_index ++;
Stack.push(n);
in_stack[n] = 1;
for (int i = 0; i < graph[n].size(); ++ i) {
int node = graph[n][i];
if (dfs_time[node] == -1) {
recursive_tarjan(node);
lowlink[n] = min(lowlink[n], lowlink[node]);
}
else if (in_stack[node]) {
lowlink[n] = min(lowlink[n], lowlink[node]);
}
}
if (dfs_time[n] == lowlink[n]) {
new_component.clear();
int node;
do {
new_component.push_back(node = Stack.top());
Stack.pop(), in_stack[node] = 0;
}
while (node != n);
components.push_back(new_component);
}
}
void tarjan_algorithm() {
for (int i = 0; i < nodes_count; ++ i) {
if (dfs_time[i] == -1) {
recursive_tarjan(i);
}
}
}
void init_data() {
lowlink.resize(nodes_count);
for (int i = 0; i < nodes_count; i++) {
dfs_time.push_back(-1);
in_stack.push_back(0);
}
}
int main(void)
{
read_data();
init_data();
tarjan_algorithm();
print_data();
return 0;
}