Pagini recente » Atasamentele paginii lpaths | Cod sursa (job #1830297) | Diferente pentru problema/petsoft intre reviziile 9 si 6 | Cod sursa (job #1151453) | Cod sursa (job #3321303)
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m;
vector<vector<int>> graf, graf_t, output_comps;
vector<int> nodes_by_exit_time, which_component_for_node;
bitset<(int)(1e5 + 5)> viz;
void populate_exit_times(int node) {
viz[node] = 1;
for (const int nei : graf[node]) {
if (!viz[nei]) populate_exit_times(nei);
}
nodes_by_exit_time.push_back(node);
}
void search_graf_t(int node, int component_number) {
viz[node] = 1;
which_component_for_node[node] = component_number;
for (const int nei : graf_t[node]) {
if (!viz[nei]) search_graf_t(nei, component_number);
}
}
int main() {
cin >> n >> m;
graf.resize(n + 2);
graf_t.resize(n + 2);
which_component_for_node.resize(n + 2);
output_comps.resize(n + 2);
for (int i = 1 ; i <= m ; ++i) {
int src, dest;
cin >> src >> dest;
graf[src].push_back(dest);
graf_t[dest].push_back(src);
}
for (int i = 1 ; i <= n ; ++i) {
if (!viz[i]) populate_exit_times(i);
}
reverse(nodes_by_exit_time.begin(), nodes_by_exit_time.end());
viz.reset();
int component_number = 0;
for (const int node : nodes_by_exit_time) {
if (!viz[node]) {
search_graf_t(node, ++component_number);
}
}
for (int i = 1 ; i <= n ; ++i) {
output_comps[which_component_for_node[i]].push_back(i);
}
cout << component_number << "\n";
for (const vector<int>& comp : output_comps) {
for (int node : comp) cout << node << " ";
if (comp.size()) cout << "\n";
}
return 0;
}