Pagini recente » Cod sursa (job #2846954) | Cod sursa (job #2895043) | Cod sursa (job #2427984) | Cod sursa (job #2929303) | Cod sursa (job #2723229)
#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;
bool Sel[NMAX];
vector < int > G[NMAX], T[NMAX];
vector < int > S;
vector < int > _temp;
vector < vector < int > > Sol;
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_1 (int Node)
{
Sel[Node] = 1;
for(auto it : G[Node])
if(!Sel[it])
DFS_1(it);
S.push_back(Node);
return;
}
static inline void TopoSort ()
{
for(int i = 1; i <= N; ++i)
if(!Sel[i])
DFS_1(i);
reverse(S.begin(), S.end());
return;
}
static inline void DFS_2 (int Node)
{
Sel[Node] = 1, _temp.push_back(Node);
for(auto it : T[Node])
if(!Sel[it])
DFS_2(it);
return;
}
static inline void Solve ()
{
TopoSort();
for(int i = 1; i <= N; ++i)
Sel[i] = 0;
for(auto it : S)
if(!Sel[it])
{
_temp.clear();
DFS_2(it);
Sol.push_back(_temp);
}
g << (int)Sol.size() << '\n';
for(auto it : Sol)
{
for(int j = 0; j < (int)it.size(); ++j)
{
g << it[j];
if(j != (int)it.size() - 1)
g << ' ';
}
g << '\n';
}
return;
}
int main()
{
Read();
Solve();
return 0;
}