Cod sursa(job #1472175)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 16 august 2015 15:21:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <cstdio>
#include <bitset>

#define Nmax 100005
#define Bmax 500005
#define BU 3666013
char Baff[BU];
int pz = BU - 1;

void Read(int &A){
    A = 0;
    while('0' > Baff[pz] || Baff[pz] > '9')
        if(++pz == BU)
            fread(Baff,1,BU,stdin),pz = 0;
    while('0' <= Baff[pz] && Baff[pz] <= '9')
    {
        A = (A<<3) + (A<<1) + Baff[pz] - 48;
        if(++pz == BU)
            fread(Baff,1,BU,stdin),pz = 0;
    }
}

using namespace std;

int G[Nmax],Gt[Nmax],CTC[Nmax],Stak[Nmax];
bitset<Nmax> used;
int DIM,vf,nctc;

class node{
public:
    int inf,next;
    node(){}
    node(int elem,int to){
        inf = elem;
        next = to;
    }
};
node Buff[Bmax];

void Add_list(int &head,int val){
    Buff[++DIM] = node(val,head);
    head = DIM;
}


int N,M;
void Read()
{
    Read(N);Read(M);
    int a,b;
    for(int i = 1; i <= M; ++i)
    {
        Read(a);Read(b);
        Add_list(G[a],b);
        Add_list(Gt[b],a);
    }
}

void DFS(int k)
{
    used[k] = 1;
    for(int v = G[k]; v; v = Buff[v].next)
        if(!used[Buff[v].inf])
            DFS(Buff[v].inf);

    Stak[++vf] = k;
}

void DFST(int k)
{
    Add_list(CTC[nctc],k);
    used[k] = 1;
    for(int v = Gt[k]; v; v = Buff[v].next)
        if(!used[Buff[v].inf])
            DFST(Buff[v].inf);


}

void Kosaraju()
{
    for(int i = 1; i <= N; ++i)
        if(!used[i])
            DFS(i);
    used = 0;
    while(vf > 0)
    {
        while(vf > 0 && used[ Stak[vf] ])
            --vf;
        if(vf == 0)
            continue;
        ++nctc;
        DFST(Stak[vf]);
    }
}

void Print()
{
    printf("%d\n",nctc);
    for(int i = 1; i <= nctc; ++i)
    {
        for(int v = CTC[i]; v; v = Buff[v].next)
            printf("%d ",Buff[v].inf);
        printf("\n");
    }
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    Read();
    Kosaraju();
    Print();

    return 0;
}