Pagini recente » Cod sursa (job #1365663) | Cod sursa (job #1603244) | Cod sursa (job #411700) | Cod sursa (job #2326204) | Cod sursa (job #1811604)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 10;
int n, m;
bool used[nmax];
vector < int > g[nmax], gt[nmax];
int cnt;
int scc[nmax];
vector < int > s;
void input() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
g[x].push_back(y);
gt[y].push_back(x);
}
}
void dfs(int node) {
used[node] = 1;
for (auto &it : g[node]) {
if (used[it]) continue;
dfs(it);
}
s.push_back(node);
}
void dfsT(int node) {
scc[node] = cnt;
for (auto &it : gt[node]) {
if (scc[it]) continue;
dfsT(it);
}
}
void solve() {
///build stack
for (int i = 1; i <= n; ++i)
if (!used[i]) dfs(i);
for (auto it = s.rbegin(); it != s.rend(); ++it)
if (!scc[*it]) cnt++, dfsT(*it);
}
void output() {
vector < int > ans[cnt+1];
for (int i = 1; i <= n; ++i)
ans[scc[i]].push_back(i);
printf("%d\n", cnt);
for (int i = 1; i <= cnt; ++i, printf("\n"))
for (auto &it : ans[i]) printf("%d ", it);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
input();
solve();
output();
return 0;
}