Pagini recente » Cod sursa (job #2603568) | Cod sursa (job #1515522) | Cod sursa (job #1681228) | Cod sursa (job #2697174) | Cod sursa (job #1743265)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define MAX_NODES 100100
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> graph[MAX_NODES];
vector <int> reversed_graph[MAX_NODES];
vector <int> components[MAX_NODES];
int dfs_time[MAX_NODES];
bool visited[MAX_NODES];
bool tarjan_visited[MAX_NODES];
int no_of_nodes;
int no_of_edges;
int number_of_components = 0;
int time_in = 0;
void dfs(int node) {
visited[node] = true;
for (int neighbor = 0; neighbor < graph[node].size(); neighbor++) {
if(visited[graph[node][neighbor]] == false) {
dfs(graph[node][neighbor]);
}
}
dfs_time[++time_in] = node;
}
void dfs_tarjan(int node) {
tarjan_visited[node] = true;
components[number_of_components].push_back(node);
for(int i=0; i<reversed_graph[node].size(); ++i) {
if (tarjan_visited[reversed_graph[node][i]] == false ) {
dfs_tarjan(reversed_graph[node][i]);
}
}
}
void tarjan() {
for(int node = 1; node <= no_of_nodes; node++) {
if(visited[node] == false) {
dfs(node);
}
}
for (int node = no_of_nodes; node > 0; node--) {
if (tarjan_visited[dfs_time[node]] == false) {
number_of_components++;
dfs_tarjan(dfs_time[node]);
}
}
}
void print_solution() {
fout<<number_of_components<<'\n';
for (int component_index=1; component_index <= number_of_components; component_index++) {
for (int node_index = 0; node_index < components[component_index].size(); node_index++) {
fout<<components[component_index][node_index]<<' ';
}
fout<<'\n';
}
}
void init_data() {
for (int index = 0; index <= no_of_nodes; index++) {
visited[index] = false;
tarjan_visited[index] = false;
}
}
void read_data() {
int node1, node2;
fin>>no_of_nodes;
fin>>no_of_edges;
for (int index = 1; index <= no_of_edges; index++) {
fin>>node1>>node2;
graph[node1].push_back(node2);
reversed_graph[node2].push_back(node1);
}
}
int main() {
read_data();
init_data();
tarjan();
print_solution();
return 0;
}