Pagini recente » Cod sursa (job #878333) | Cod sursa (job #2038659) | Cod sursa (job #1441362) | Cod sursa (job #496586) | Cod sursa (job #2713858)
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
class Tarjan {
private:
int no_nodes;
vector<vector<int> > graph;
stack<int> stack;
vector<int> node_discovery_time;
vector<int> component_discovery_time;
vector<bool> in_stack;
int time;
int total_components;
vector<vector<int> > components;
void tarjan(int node);
public:
Tarjan(vector<vector<int> > & graph);
vector<vector<int> > get_components();
int get_no_components() {return total_components;}
};
Tarjan::Tarjan(vector<vector<int> > & graph) {
no_nodes = graph.size();
this->graph = graph;
node_discovery_time.resize(no_nodes, 0);
component_discovery_time.resize(no_nodes, 0);
in_stack.resize(no_nodes, false);
time = 1;
total_components = 0;
components.resize(no_nodes);
}
void Tarjan::tarjan(int node) {
node_discovery_time[node] = time;
component_discovery_time[node] = time;
++time;
stack.push(node);
in_stack[node] = true;
for (int neighbor: graph[node]) {
if (!node_discovery_time[neighbor]) {
tarjan(neighbor);
component_discovery_time[node] =
min(component_discovery_time[node], component_discovery_time[neighbor]);
} else if (in_stack[neighbor]) {
component_discovery_time[node] =
min(component_discovery_time[node], component_discovery_time[neighbor]);
}
}
if (node_discovery_time[node] == component_discovery_time[node]) {
while (stack.top() != node) {
components[total_components].push_back(stack.top());
in_stack[stack.top()] = false;
stack.pop();
}
components[total_components].push_back(stack.top());
in_stack[stack.top()] = false;
stack.pop();
++total_components;
}
}
vector<vector<int> > Tarjan::get_components() {
for (int i = 0; i < no_nodes; ++i) {
if (!node_discovery_time[i]) {
tarjan(i);
}
}
return components;
}
int main() {
FILE * f;
int n, m, x, y;
f = fopen("ctc.in", "r");
fscanf(f, "%d%d", &n, &m);
vector<vector<int> > graph(n);
for (int i = 0; i < m; ++i) {
fscanf(f, "%d%d", &x, &y);
--x;
--y;
graph[x].push_back(y);
}
fclose(f);
Tarjan tarjan(graph);
vector<vector<int> > components = tarjan.get_components();
f = fopen("ctc.out", "w");
fprintf(f, "%d\n", tarjan.get_no_components());
for (int i = 0; i < n; ++i) {
if (!components[i].size()) {
continue;
}
for (int node: components[i]) {
fprintf(f, "%d ", node + 1);
}
fprintf(f, "\n");
}
fclose(f);
return 0;
}