Pagini recente » Cod sursa (job #985686) | Cod sursa (job #1060652) | Cod sursa (job #3241097) | Cod sursa (job #2446625) | Cod sursa (job #488254)
Cod sursa(job #488254)
#include <cstdio>
#include <vector>
using namespace std;
#define NMAX 100002
int n,m,viz[NMAX],N,S[NMAX],sol;
vector <int> G[NMAX],GT[NMAX],CTC[NMAX];
void read();
void print();
void kosaraju();
void DFS1();
void DFS2();
int main(){
read();
kosaraju();
print();
return 0;
}
void DFS1(int nod){
viz[nod]=1;
for(int i =0; i< (int) G[nod].size() ; ++i){
if(!viz[G[nod][i]]){
DFS1(G[nod][i]);
}
}
S[++N]=nod;
}
void DFS2(int nod){
viz[nod]=0;
CTC[sol].push_back(nod);
for(int i =0; i< (int) GT[nod].size() ; ++i){
if(viz[GT[nod][i]]){
DFS2(GT[nod][i]);
}
}
}
void kosaraju(){
for(int i=1 ; i<=n ; ++i ){
if(!viz[i]){
DFS1(i);
}
}
for( ; N>0 ; --N){
if(viz[S[N]]){
sol++;
DFS2(S[N]);
}
}
}
void read(){
int nod1,nod2;
freopen("ctc.in", "r", stdin);
scanf("%d %d ", &n, &m);
for(int i=1; i<=m; ++i){
scanf("%d %d ", &nod1, &nod2);
G[nod1].push_back(nod2);
GT[nod2].push_back(nod1);
}
}
void print(){
freopen("ctc.out", "w", stdout);
printf("%d \n", sol);
for(int i=1; i<=sol ; ++i){
for(int j=0; j < (int) CTC[i].size() ; ++j){
printf("%d ", CTC[i][j]);
}
printf("\n");
}
/*for(int i=1; i<=n ; ++i){
for(int j=0 ; j< (int) GT[i].size() ; j++){
printf("%d ", GT[i][j]);
}
printf("\n");
}*/
}