Pagini recente » Cod sursa (job #2916940) | Cod sursa (job #2051633) | Cod sursa (job #1723667) | Cod sursa (job #2780092) | Cod sursa (job #1856183)
#include<fstream>
#include<vector>
#include<iostream>
#include<chrono>
#include<queue>
#include<algorithm>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> G[100010],GT[100010],stk;
int viz[100010];
int nr = 1;
vector<int> rez[100010];
void sort_top(int x)
{
viz[x] = 1;
for (int i = 0; i < G[x].size(); ++i)
if (!viz[G[x][i]])
sort_top(G[x][i]);
stk.push_back(x);
}
void DFS(int x)
{
viz[x] = 1;
for (int i = 0; i < GT[x].size(); ++i)
{
if (!viz[GT[x][i]])
DFS(GT[x][i]);
}
rez[nr].push_back(x);
}
int main()
{
int N, M;
in >> N >> M;
for (int i = 1; i <= M; ++i)
{
int x, y;
in >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
for (int i = 1; i <= N; ++i)
{
if (!viz[i])
sort_top(i);
}
for (int i = 1; i <= N; ++i)
viz[i] = 0;
for (int i = stk.size() - 1; i >= 0; --i)
{
if (!viz[stk[i]])
{
DFS(stk[i]);
++nr;
}
}
out << nr-1 << "\n";
for (int i = 1; i <= nr; ++i)
{
for (int j = 0; j < rez[i].size(); ++j)
out << rez[i][j] << " ";
out << "\n";
}
return 0;
}