Cod sursa(job #1982289)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 18 mai 2017 08:15:11
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include <fstream>
#include <stdint.h>
#define nmax 100001
#define mmax 200001
using namespace std;
fstream f1("ctc.in", ios::in);
fstream f2("ctc.out", ios::out);
int32_t aux[nmax], cap[nmax], auxt[nmax], capt[nmax], nrcomp;
int32_t v[mmax], vt[mmax], lista[nmax], l;
int32_t n, m, viz[nmax], viz2[nmax];
struct muc
{
    int32_t x, y;
}muc[mmax];
///creezi 2 liste de adiacenta: una a grafului normal si una a grafului transpus
///viz2[i]= nr comp conexe din care face parte nodul i
void citire()
{
    int32_t i, x, y;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y;
        aux[x]++;
        auxt[y]++;
        muc[i].x=x;
        muc[i].y=y;
    }
}
void lista_ad()
{
    int32_t i, x, y;
    cap[1]=1;
    for(i=2; i<=n+1; i++)
        {
            cap[i]=cap[i-1]+ aux[i-1];
            aux[i-1]=cap[i-1];
        }
    for(i=1; i<=m; i++)
    {
        x=muc[i].x;
        y=muc[i].y;
        v[aux[x]]=y;
        aux[x]++;
    }
}
void lista_ad_t()
{
    int32_t i, x, y;
    capt[1]=1;
    for(i=2; i<=n+1; i++)
        {
            capt[i]=capt[i-1]+ auxt[i-1];
            auxt[i-1]=capt[i-1];
        }
    for(i=1; i<=m; i++)
    {
        x=muc[i].x;
        y=muc[i].y;
        vt[auxt[y]]=x;
        auxt[y]++;
    }
}
void dfs(int32_t nod)
{
    int32_t i;
    viz[nod]=1;
    for(i=cap[nod]; i<cap[nod+1]; i++)
        if(!viz[v[i]])
    {
        dfs(v[i]);
    }
    l++;
    lista[l]=nod;
}
void dfs_transpus(int32_t nod)
{
    int32_t i;
    viz2[nod]=nrcomp;
    for(i=capt[nod]; i<capt[nod+1]; i++)
        if(!viz2[vt[i]])
    {
        viz2[vt[i]]=nrcomp;
        dfs_transpus(vt[i]);
    }
}
void afisare()
{
    int32_t i, j;
    f2<<nrcomp<<"\n";
    for(i=1; i<=nrcomp; i++)
    {
        for(j=1; j<=n; j++)
            if(viz2[j]==i) f2<<j<<"  ";
        f2<<"\n";
    }
}
int main()
{
    int32_t i;
    citire();
    lista_ad();
    lista_ad_t();
    for(i=1; i<=n; i++)
        if(!viz[i])
            dfs(i);

    for(i=n; i>=1; i--)
        if(!viz2[lista[i]])
    {
        nrcomp++;
        dfs_transpus(lista[i]);
    }
    afisare();
    return 0;
}