Pagini recente » Cod sursa (job #2598964) | Cod sursa (job #201422) | Cod sursa (job #884446) | Cod sursa (job #157941) | Cod sursa (job #2500946)
#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];
bool Sel[NMAX], Sel1[NMAX], Sel2[NMAX];;
int Elem, V[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)
{
Sel1[Node] = 1;
V[++Elem] = Node;
for(auto it : G[Node])
if(!Sel1[it])
DFS1(it);
return;
}
static inline void DFS2 (int Node)
{
Sel2[Node] = 1;
if(!Sel1[Node])
V[++Elem] = Node;
for(auto it : T[Node])
if(!Sel2[it])
DFS2(it);
return;
}
static inline void Solve ()
{
for(int i = 1; i <= N; ++i)
if(!Sel[i])
{
++cnt;
Elem = 0;
DFS1(i);
DFS2(i);
for(int j = 1; j <= Elem; ++j)
if(Sel1[V[j]] && Sel2[V[j]])
{
Sel[V[j]] = 1;
Sol[cnt].push_back(V[j]);
}
else
Sel1[V[j]] = Sel2[V[j]] = 0;
}
return;
}
static inline void Write ()
{
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;
}