Cod sursa(job #1824658)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 8 decembrie 2016 10:50:28
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 3.28 kb
#include <fstream>
#include <stdint.h>
using namespace std;
fstream f1("ctc.in", ios::in);
fstream f2("ctc.out", ios::out);
///componenete tari-conexe, algoritmul lui kosaraju
///idee: iti faci un vector nrc[<n>] care tine minte din a cata comp conexa face parte nodul i
///pentru fiecare nod i, cu nrc[i]=0, identifici cu 2 parcurgeri bfs recursive succesorii si predecesorii nodului
///nr se reactualizeaza la fiecare rulare a for-ului si reprezinta nr de componente conexe init 0
///s[x]=nr daca nodul x este succesor pt i
///p[x]=nr daca nodul y este predecesor pentru i
///s[i]=nr, p[i]=nr implicit
///daca nodul x este si succ si predecesor, atunci x face parte din aceeasi componenta conexa ca si nodul i
///deoarece poti ajunge pe un drum de la x la i, dar si de la i la x
///pui in nrc[i] si nrcc[x], cu propr ca s[x]=nr si p[x]=nr, val nr
///pt p[x]==0 sau s[x]==0 pui p[x]=s[x]=0///nodul x nu face parte din nicio comp conexa
int32_t n, m, s[100001], p[100001], nrc[100001], v1[200001],v2[200001], nr, cap1[100001],cap2[100001];
struct muchie
{
    int32_t  x, y;
}muc[200001];
///v1 este o lista de adiacenta care tine minte vecini x->y, y este vecin al lui x, dar nu si invers
///v1 are dim nr de muchii
///cap1[i] tine minte indicii de unde incep vecinii nodului i
///v2 este lista de adiacenta a grafului transpus y->x
void bfss(int32_t i)
{
    int32_t j;
    for(j=cap1[i]; j<cap1[i+1]; j++)
        if(!s[v1[j]])
       {
            s[v1[j]]=nr;
            bfss(v1[j]);
       }
}
void bfsp(int32_t i)
{
    int32_t j;
    for(j=cap2[i]; j<cap2[i+1]; j++)
        if(!p[v2[j]])
       {
           ///v2[j] este tata pentru i
            p[v2[j]]=nr;
            bfsp(v2[j]);
       }
}
int main()
{
    int32_t i, x, y, j;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y;
        ///s[i] devine in final nr succ nodul i
        ///in muc tii minte muchiile provizoriu
        ///p[i] devine in final nr pred
        s[x]++;
        p[y]++;
        muc[i].x=x;
        muc[i].y=y;
    }
    ///construiesti vect cap1 si cap2
    cap1[1]=1;
    cap2[1]=1;

    for(i=1; i<=n; i++)///ca sa stii si cap[n+1]
        {
            cap1[i+1]=cap1[i]+s[i];
            s[i]=cap1[i];

            cap2[i+1]=cap2[i]+p[i];
            p[i]=cap2[i];
        }

    ///construiesti lista de adiacenta
    for(i=1; i<=m; i++)
    {
        x=muc[i].x;
        y=muc[i].y;
        v1[s[x]]=y;
        s[x]++;

        ///x este predecesor al lui y, x->y
        v2[p[y]]=x;
        p[y]++;
    }
    for(i=1; i<=n; i++) {s[i]=0;p[i]=0;}
    ///pentru fiecare nod care nu se afla intr o comp conexa
    for(i=1; i<=n; i++)
        if(!nrc[i])
    {
        nr++;
        nrc[i]=nr;
        s[i]=nr;
        p[i]=nr;
        ///afli predecesorii si succesorii nodului i
        bfss(i);
        bfsp(i);
        ///nodul j face parte din componenta conexa nr sau nu
        for(j=1; j<=n; j++)
            if((p[j]==nr)&&(s[j]==nr)) nrc[j]=nr;
            else if((p[j]==0)||(s[j]==0)) {p[j]=s[j]=0;}
    }
    f2<<nr<<"\n";
    ///afisezi pe cate o linie nodurile din fiecare comp conexa
    for(i=1; i<=nr; i++)
    {
        for(j=1; j<=n; j++)
            if(nrc[j]==i) f2<<j<<" ";
        f2<<"\n";
    }
    return 0;
}