Pagini recente » Cod sursa (job #2980256) | Borderou de evaluare (job #2009) | Cod sursa (job #2620027) | Cod sursa (job #3270386) | Cod sursa (job #2870705)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
typedef vector < int > VI;
const int NMAX = 1e5 + 1;
int N;
VI G[NMAX], GT[NMAX];
bool Sel[NMAX];
VI List;
VI _temp;
vector < VI > Sol;
static inline void Read ()
{
f.tie(nullptr);
f >> N;
int M = 0;
f >> M;
for(int i = 1; i <= M; ++i)
{
int u = 0, v = 0;
f >> u >> v;
G[u].push_back(v), GT[v].push_back(u);
}
return;
}
static inline void DFS (int Node)
{
Sel[Node] = 1;
for(auto it : G[Node])
if(!Sel[it])
DFS(it);
List.push_back(Node);
return;
}
static inline void Go (int Node)
{
Sel[Node] = 0;
_temp.push_back(Node);
for(auto it : GT[Node])
if(Sel[it])
Go(it);
return;
}
static inline void Solve ()
{
for(int i = 1; i <= N; ++i)
if(!Sel[i])
DFS(i);
reverse(List.begin(), List.end());
for(auto it : List)
if(Sel[it])
_temp.clear(), Go(it), Sol.push_back(_temp);
return;
}
static inline void Write ()
{
g << (int)Sol.size() << '\n';
for(auto i : Sol)
{
sort(i.begin(), i.end());
for(int j = 0; j < (int)i.size(); ++j)
{
g << i[j];
if(j != (int)i.size() - 1)
g << ' ';
}
g << '\n';
}
return;
}
int main()
{
Read();
Solve();
Write();
return 0;
}