Pagini recente » Cod sursa (job #3031454) | Cod sursa (job #2778738) | Cod sursa (job #2418254) | Cod sursa (job #765093) | Cod sursa (job #1089376)
#include <cstdio>
#include <vector>
#define NMAX 100001
using namespace std;
bool vizitat[NMAX];
int n,m,nr;
int k;
vector < vector < int > > Graf;
vector < vector < int > > Graft;
vector < int > M[NMAX];
int postordine[NMAX];
inline void read(){
int x,y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
Graf.resize(n+1);
Graft.resize(n+1);
for(register int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
Graf[x].push_back(y);
Graft[y].push_back(x);
}
}
void DFS(int nod){
vizitat[nod] = 1;
for(vector <int> :: iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
if(!vizitat[*it])
DFS(*it);
postordine[++k] = nod;
}
void DFST(int nod){
vizitat[nod] = 0;
M[nr].push_back(nod);
for(vector < int > ::iterator it = Graft[nod].begin();it!=Graft[nod].end();++it)
if(vizitat[*it])
DFST(*it);
}
void solve(){
for(register int i=1;i<=n;++i)
if(!vizitat[i])
DFS(i);
for(register int i=n;i>0;--i){
if(vizitat[postordine[i]]){
++nr;
DFST(postordine[i]);
}
}
}
void write(){
int length;
printf("%d\n",nr);
for(register int i=1;i<=nr;++i){
length = M[i].size();
for(register int j=0;j<length;++j)
printf("%d ",M[i][j]);
printf("\n");
}
}
int main(){
read();
solve();
write();
return 0;
}