Cod sursa(job #767147)

Utilizator igsifvevc avb igsi Data 12 iulie 2012 20:42:29
Problema Componente tare conexe Scor 60
Compilator c Status done
Runda Arhiva educationala Marime 1.41 kb
#include<stdlib.h>
#include<stdio.h>

struct node{
    int value;
    struct node *next;
} *G[100001], *Gt[100001];
int N, nrComp, visited[100001], stack[100001];
FILE *in, *out;

void df1(int i)
{
    struct node *p;
    visited[i] = -1;

    for(p = G[i]; p; p = p->next)
        if(visited[p->value] == 0)
            df1(p->value);
    stack[++stack[0]] = i;
}

void df2(int i)
{
    struct node *p;
    visited[i] = nrComp;
    
    for(p = Gt[i]; p; p = p->next)
        if(visited[p->value] == -1)
            df2(p->value);
}

int main(){
    int i, M, a, b;
    struct node *p;
    
    in = fopen("ctc.in", "r");
    out = fopen("ctc.out", "w");

    fscanf(in, "%d %d", &N, &M);
    for(; M; --M){
        fscanf(in, "%d %d", &a, &b);
        p = malloc(sizeof(struct node));
        p->value = b;
        p->next = G[a];
        G[a] = p;

        p = malloc(sizeof(struct node));
        p->value = a;
        p->next = Gt[b];
        Gt[b] = p;
    }

    for(i = 1; i <= N; ++i)
        if(!visited[i]){
            df1(i);
        }

    for(nrComp = 0, i = N; i; --i)
        if(visited[stack[i]] == -1){
            ++nrComp;
            df2(stack[i]);
        }

    fprintf(out, "%d\n", nrComp);
    for(i = 1; i <= nrComp; ++i)
    {
        for(a = 1; a <= N; ++a)
            if(visited[a] == i)
                fprintf(out, "%d ", a);
        fprintf(out, "\n");
    }

    fclose(in);
    fclose(out);
    return 0;
}