Pagini recente » Cod sursa (job #2699498) | Cod sursa (job #1165283) | Cod sursa (job #1704934) | Cod sursa (job #953423) | Cod sursa (job #2305926)
#include <stdio.h>
#include <vector>
#include <cstring>
#include <algorithm>
#define SZ(x) ((int)(x.size()))
#define nmax 100010
using namespace std;
int n, m;
bool viz[nmax];
vector<vector<int>> answer;
vector <int> order, graph[nmax], graph2[nmax];
void dfs1(int node)
{
viz[node] = true;
for (int i = 0; i < SZ(graph[node]); i++)
if (!viz[graph[node][i]]) dfs1(graph[node][i]);
order.push_back(node);
}
void dfs2(int node)
{
viz[node] = true;
for (int i = 0; i < SZ(graph2[node]); i++)
if (!viz[graph2[node][i]]) dfs2(graph2[node][i]);
answer[answer.size() - 1].push_back(node);
}
int main()
{
//freopen("ctc.in", "r", stdin);
//freopen("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d %d", &x, &y);
graph[x].push_back(y);
graph2[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!viz[i]) dfs1(i);
memset(viz, 0, sizeof(viz));
for (int i = n - 1; i >= 0; i--) {
int v = order[i];
if (!viz[v]) {
answer.push_back(vector <int>());
dfs2(v);
}
}
printf("%d\n", SZ(answer));
for (int i = 0; i < SZ(answer); i++) {
for (int j = 0; j < SZ(answer[i]); j++) printf("%d ", answer[i][j]);
printf("\n");
}
return 0;
}