Pagini recente » Cod sursa (job #2627693) | Cod sursa (job #2731429) | Cod sursa (job #1225781) | Cod sursa (job #2670303) | Cod sursa (job #2157805)
#include <stdio.h>
#include <stdlib.h>
#define NMax 100003
typedef struct node{
int value;
struct node *next;
}Node;
Node *G[NMax];
Node *GT[NMax];
Node *ctc[NMax];
int n,m,x,y,top,nr;
int st[NMax],viz[NMax];
void insert(Node **first,int value){
if(*first == NULL){
Node *aux;
aux = (Node *)malloc(1 * sizeof(Node));
aux->value = value;
aux->next = NULL;
(*first) = aux;
return;
}
Node *aux;
aux = (Node *)malloc(1 * sizeof(int));
aux->value = value;
aux->next = (*first);
(*first) = aux;
}
void print_list(Node *first){
for(Node *p = first; p; p = p->next){
printf("%d ",p->value);
}
printf("\n");
}
void dfs(int nod){
viz[nod] = 1;
for(Node *p = G[nod]; p; p = p->next){
if(!viz[p->value]){
dfs(p->value);
}
}
st[++top] = nod;
}
void dfsT(int nod){
viz[nod] = 1;
for(Node *p = GT[nod]; p; p = p->next){
if(!viz[p->value]){
dfsT(p->value);
}
}
insert(&ctc[nr],nod);
}
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; ++i){
G[i] = NULL;
GT[i] = NULL;
}
for(int i = 1; i <= m; ++i){
scanf("%d%d",&x,&y);
insert(&G[x],y);
insert(>[y],x);
}
for(int i = 1; i <= n; ++i){
if(!viz[i]){
dfs(i);
}
}
for(int i = 1; i <= n; ++i){
viz[i] = 0;
}
for(int i = n; i >= 1; --i){
if(!viz[st[i]]){
nr++;
dfsT(st[i]);
}
}
printf("%d\n",nr);
for(int i = 1; i <= nr; ++i){
print_list(ctc[i]);
}
return 0;
}