Pagini recente » Cod sursa (job #2693265) | Cod sursa (job #290214) | Cod sursa (job #12036) | Istoria paginii runda/oni_mixed_1/clasament | Cod sursa (job #2500972)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int BSIZE = (1 << 16), NMAX = 1e5 + 5;
int N, M, x, y, cnt = 0;
vector < int > G[NMAX], T[NMAX];
vector < int > V;
bool Sel[NMAX];
int Where[NMAX];
vector < int > Sol[NMAX];
///
int pos = BSIZE - 1;
char buff[BSIZE];
static inline char Char ()
{
++pos;
if(pos == BSIZE)
{
pos = 0;
fread(buff, 1, BSIZE, stdin);
}
return buff[pos];
}
static inline int Int ()
{
int r = 0;
for(;;)
{
char ch = Char();
if(isdigit(ch))
{
r = (ch - '0');
break;
}
}
for(;;)
{
char ch = Char();
if(isdigit(ch))
r = r * 10 + (ch - '0');
else
break;
}
return r;
}
///
static inline void Read ()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
N = Int();
M = Int();
for(int i = 1; i <= M; ++i)
{
x = Int();
y = Int();
G[x].push_back(y);
T[y].push_back(x);
}
return;
}
static inline void DFS1 (int Node)
{
Sel[Node] = 1;
for(auto it : G[Node])
if(!Sel[it])
DFS1(it);
V.push_back(Node);
return;
}
static inline void DFS2 (int Node, int ord)
{
Where[Node] = ord;
for(auto it : T[Node])
if(!Where[it])
DFS2(it, ord);
return;
}
static inline void Solve ()
{
for(int i = 1; i <= N; ++i)
if(!Sel[i])
DFS1(i);
for(int i = (int)V.size() - 1; i >= 0; --i)
if(!Where[V[i]])
{
++cnt;
DFS2(V[i], cnt);
}
return;
}
static inline void Load ()
{
for(int i = 1; i <= N; ++i)
Sol[Where[i]].push_back(i);
return;
}
static inline void Write ()
{
Load();
printf("%d\n", cnt);
for(int i = 1; i <= cnt; ++i)
{
for(auto it : Sol[i])
printf("%d ", it);
printf("\n");
}
return;
}
int main()
{
Read();
Solve();
Write();
return 0;
}