Cod sursa(job #1854068)

Utilizator Coroian_DavidCoroian David Coroian_David Data 22 ianuarie 2017 13:05:54
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.49 kb
#include <cstdio>

using namespace std;

FILE *f, *g;

struct nod
{
    int nr;

    nod *urm;
};

nod *p, *lista[100009];

nod *compCTC[100009];

int d[100002];
int stk[1000002], stkLen;

bool onStack[100009];

void add(int a, int b)
{
    p = new nod;

    p -> urm = lista[a];

    p -> nr = b;

    lista[a] = p;
}

int n, m;
int CTC;

inline int mna(int a, int b)
{
    return (a < b ? a : b);
}

void readFile()
{
    f = fopen("ctc.in", "r");

    fscanf(f, "%d%d", &n, &m);

    int i;
    int a, b;
    for(i = 1; i <= m; i ++)
    {
        fscanf(f, "%d%d", &a, &b);

        add(a, b);
    }

    fclose(f);
}

int DFS(int nodul, int depth)
{
    d[nodul] = depth;
    stk[++ stkLen] = nodul;
    onStack[nodul] = true;

    nod *p = lista[nodul];

    ///Pentru fiecare vecin
    while(p != 0)
    {
        ///Daca e muchie "arbore"
        if(d[p -> nr] == -1)
        {
            d[nodul] = mna(d[nodul], DFS(p -> nr, depth + 1));
        }

        ///Daca e muchie "inapoi"
        else
            if(onStack[p -> nr] == true)
            {
                d[nodul] = mna(d[nodul], d[p -> nr]);
            }
        ///Altfel e muchie ianinte sau cross

        p = p -> urm;
    }

    ///Nodul este radacina unei CTC
    if(d[nodul] == depth)
    {
        ///Eticheteaza si scoate CTC de pe stiva
        int nodVecin;
        CTC ++;
        do
        {
            nodVecin = stk[stkLen --];

            onStack[nodVecin] = false;

            ///Adauga la CTCa curenta
            p = new nod;
            p -> nr = nodVecin;
            p -> urm = compCTC[CTC];
            compCTC[CTC] = p;
        }
        while(nodVecin != nodul);
    }

    return d[nodul];
}


void tarzjan()
{
    int i;
    for(i = 1; i <= n; i ++)
    {
        ///Pentru fiecare nod nevizitat
        if(d[i] == -1)
            DFS(i, 0);
    }
}

void init0()
{
    int i;
    for(i = 1; i <= n; i ++)
        d[i] = -1;
}

void solve()
{
    init0();

    tarzjan();
}

void printFile()
{
    g = fopen("ctc.out", "w");

    fprintf(g, "%d\n", CTC);

    int i;
    for(i = 1; i <= CTC; i ++)
    {
        p = compCTC[i];

        while(p != 0)
        {
            fprintf(g, "%d ", p -> nr);

            p = p -> urm;
        }

        fprintf(g, "\n");
    }

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}