Pagini recente » Cod sursa (job #2176128) | Cod sursa (job #3236154) | Cod sursa (job #3178200) | Cod sursa (job #235001) | Cod sursa (job #3215617)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int DIM = 100010;
int n, m;
int scc[DIM];
vector<int> l[DIM], t[DIM], nodes;
bool visited[DIM];
void dfs1(int node) {
visited[node] = true;
for (auto adjNode : l[node])
if (!visited[adjNode])
dfs1(adjNode);
nodes.push_back(node);
}
void dfs2(int node, int val) {
visited[node] = true;
scc[node] = val;
for (auto adjNode : t[node])
if (!visited[adjNode])
dfs2(adjNode, val);
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
l[x].push_back(y);
t[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!visited[i])
dfs1(i);
memset(visited, false, sizeof(visited));
int sccCount = 0;
for (auto it = nodes.rbegin(); it != nodes.rend(); it++) {
int node = *it;
if (!visited[node])
dfs2(node, ++sccCount);
}
fout << sccCount << '\n';
for (int i = 1; i <= sccCount; i++) {
for (int j = 1; j <= n; j++)
if (scc[j] == i)
fout << j << ' ';
fout << '\n';
}
return 0;
}