Pagini recente » Cod sursa (job #462771) | Cod sursa (job #3189339) | Cod sursa (job #1152671) | Cod sursa (job #1444918) | Cod sursa (job #2738591)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 1e5 + 1;
int N, M;
vector < int > G[NMAX], T[NMAX];
bool Sel[NMAX];
vector < int > V;
vector < int > Sol[NMAX];
static inline void Read ()
{
f.tie(nullptr);
f >> N >> M;
for(int i = 1; i <= M; ++i)
{
int X = 0, Y = 0;
f >> X >> Y;
G[X].push_back(Y), T[Y].push_back(X);
}
return;
}
static inline void DFS (int Node)
{
Sel[Node] = 1;
for(auto it : G[Node])
if(!Sel[it])
DFS(it);
V.push_back(Node);
return;
}
static inline void TopoSort ()
{
for(int i = 1; i <= N; ++i)
if(!Sel[i])
DFS(i);
reverse(V.begin(), V.end());
return;
}
static inline void Reset ()
{
for(int i = 1; i <= N; ++i)
Sel[i] = 0;
return;
}
static inline void Go (int Node, int Id)
{
Sel[Node] = 1;
Sol[Id].push_back(Node);
for(auto it : T[Node])
if(!Sel[it])
Go(it, Id);
return;
}
static inline void Solve ()
{
Reset();
int cnt = 0;
for(auto it : V)
if(!Sel[it])
Go(it, ++cnt);
g << cnt << '\n';
for(int i = 1; i <= cnt; ++i)
{
for(int j = 0; j < (int)Sol[i].size(); ++j)
{
g << Sol[i][j];
if(j != (int)Sol[i].size() - 1)
g << ' ';
}
g << '\n';
}
return;
}
int main ()
{
Read();
TopoSort();
Solve();
return 0;
}