Pagini recente » Cod sursa (job #799638) | Cod sursa (job #641794) | Cod sursa (job #2713847) | Cod sursa (job #2119860) | Cod sursa (job #1419713)
#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 100001
using namespace std;
using Graph = vector<vector<int> >;
ifstream in("ctc.in");
ofstream out("ctc.out");
Graph G(MAXN), Gt(MAXN), stronglyCtc(MAXN);
int N, M, currTime, currentCtc;
vector<int> visited(MAXN, 0), order(MAXN, 0);
void dfs(int source)
{
visited[source] = 1;
for (auto &node : G[source])
if (!visited[node])
dfs(node);
order[++currTime] = source;
}
void dfsT(int source)
{
visited[source] = 0;
stronglyCtc[currentCtc].push_back(source);
for (auto &node : Gt[source])
if (visited[node])
dfsT(node);
}
int main()
{
in >> N >> M;
int x, y;
for (int i = 1; i <= M; i++) {
in >> x >> y;
G[x].push_back(y);
Gt[y].push_back(x);
}
for (int i = 1; i <= N; i++)
if (!visited[i])
dfs(i);
for (int i = N; i >= 1; i--)
if (visited[order[i]]) {
++currentCtc;
dfsT(order[i]);
}
out << currentCtc << '\n';
for (int i = 1; i <= currentCtc; i++) {
for (auto &node : stronglyCtc[i])
out << node << " ";
out << '\n';
}
return 0;
}