Cod sursa(job #2157805)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 9 martie 2018 22:24:38
Problema Componente tare conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.81 kb
#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(&GT[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;
}