Pagini recente » Cod sursa (job #1849848) | Rating Pavel Iulia (Iulia777) | Cod sursa (job #1475839) | Cod sursa (job #331956) | Cod sursa (job #2380980)
#include <bits/stdc++.h>
#define LIM 1<<17
/// TONI BO$$ was here
/// #MLC
using namespace std;
char BUF[LIM];
int poz;
inline char getChar(){
poz++;
if(poz>=LIM){
fread(BUF,LIM,1,stdin);
poz=0;
}
return BUF[poz];
}
inline int getNr(){
int r=0, semn=1;
char ch=getChar();
while(isdigit(ch)==0 && ch!='-') ch=getChar();
if(ch=='-'){
semn=-1;
ch=getChar();
}
while(isdigit(ch)!=0){
r=r*10+semn*(ch-'0');
ch=getChar();
}
return r;
}
vector <int> G[100001];
vector <int> Gt[100001];
int f[100001],ctc;
vector <int> steve;
vector <int> rez[100001];
void dfs1(int i)
{
f[i]=1;
for(auto it : G[i])
if(!f[it])
dfs1(it);
steve.push_back(i);
}
void dfs2(int i)
{
f[i]=ctc;
for(auto it : Gt[i])
if(!f[it])
dfs2(it);
rez[ctc].push_back(i);
}
int main()
{
int n,m,i,x,y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
poz=LIM;
n=getNr();
m=getNr();
for(i=1; i<=m; i++)
{
x=getNr();
y=getNr();
G[x].push_back(y);
Gt[y].push_back(x);
}
for(i=1; i<=n; i++)
if(!f[i])
dfs1(i);
for(i=1; i<=n; i++)
f[i]=0;
while(!steve.empty())
{
int z=steve.back();
steve.pop_back();
if(f[z])
continue ;
++ctc;
f[z]=ctc;
dfs2(z);
}
printf("%d\n",ctc);
for(i=1; i<=ctc; i++)
{
for(auto it : rez[i])
printf("%d ",it);
printf("\n");
}
return 0;
}