Pagini recente » Cod sursa (job #3289291) | Cod sursa (job #2042419) | Cod sursa (job #2196097) | Cod sursa (job #2384613) | Cod sursa (job #3300715)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<vector<int>> g, gt;
stack<int> nodes;
vector<int> viz;
void dfs(int node) {
viz[node] = 1;
for (int neigh : g[node]) {
if (!viz[neigh]) {
dfs(neigh);
}
}
nodes.push(node);
}
void create_gt() {
gt.resize(n + 1);
for (int i = 1; i <= n; i++) {
for (int y : g[i]) {
gt[y].push_back(i);
}
}
}
void ctc_dfs(int node, int count) {
viz[node] = count;
for (int neigh : gt[node]) {
if (!viz[neigh]) {
ctc_dfs(neigh, count);
}
}
}
int main() {
fin >> n >> m;
g.resize(n + 1);
viz.resize(n + 1, 0);
for (int i = 0; i < m; i++) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
}
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
dfs(i);
}
}
fill(viz.begin(), viz.end(), 0);
create_gt();
int count = 1;
while (!nodes.empty()) {
int start = nodes.top();
nodes.pop();
if (!viz[start]) {
ctc_dfs(start, count);
count++;
}
}
vector<vector<int>> components(count);
for (int i = 1; i <= n; i++) {
components[viz[i]].push_back(i);
}
fout << count - 1 << '\n';
for (int i = 1; i < count; i++) {
for (int node : components[i]) {
fout << node << " ";
}
fout << '\n';
}
return 0;
}