Pagini recente » Cod sursa (job #2636565) | Cod sursa (job #833947) | Cod sursa (job #59927) | Cod sursa (job #3147950) | Cod sursa (job #1810260)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000 + 1;
vector<int> G[MAX_N];
vector<int> GT[MAX_N];
vector<int> comp[MAX_N];
bool visited[MAX_N];
vector<int> postorder;
int N, M, C;
void dfs(int node){
visited[node] = true;
for (int son : G[node])
if (!visited[son])
dfs(son);
postorder.push_back(node);
}
void dfsT(int node){
visited[node] = false;
for (int son : GT[node])
if (visited[son])
dfsT(son);
comp[C].push_back(node);
}
void CTC(){
for (int i = 1; i <= N; i++)
if (!visited[i])
dfs(i);
reverse(postorder.begin(), postorder.end());
for (int node : postorder){
if (visited[node]){
C++;
dfsT(node);
}
}
}
int main()
{
ifstream in("ctc.in");
ofstream out("ctc.out");
in >> N >> M;
for (int i = 0; i < M; i++){
int u, v;
in >> u >> v;
G[u].emplace_back(v);
GT[v].emplace_back(u);
}
CTC();
out << C << "\n";
for (int i = 1; i <= C; i++){
for (int x : comp[i])
out << x << " ";
out << "\n";
}
return 0;
}