Cod sursa(job #2612379)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 8 mai 2020 21:46:20
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>

const int NMAX = 100000;

using namespace std;

ifstream cin("ctc.in");

ofstream cout("ctc.out");

struct nod
{

    int x;

    nod* next;

};



nod* G[NMAX + 1];///G[i] lista vec nodului 1
nod* GT[NMAX + 1];///GT[i] lista vecinilor nodului i
nod* CTC[NMAX + 1];///CTC[i] lista comp tare conexe

int N, M, nrc, nr, post[NMAX + 1];

bool viz[NMAX + 1];

void add(nod*& cap_lst, int nod_add)
{

    nod* p;

    p = new nod;

    p->x = nod_add;

    p->next = cap_lst;

    cap_lst = p;

}

void citire()
{
    cin >> N >> M;

    for(int i = 1 ; i <= M ; i ++)
    {
        int x, y;

        cin >> x >> y;

        add(G[x], y);
        add(GT[y], x);
    }
}

void DFS(int vf)
{
    viz[vf] = 1;

    for(nod* p = G[vf] ; p != NULL ; p = p -> next)
        if(viz[p->x])
            DFS(p->x);

    pst[++nr] = vf;
}


void DFSt(int vf)
{

    viz[vf] = 0;

    add(CTC[nrc], vf);

    for (nod* p = GT[vf]; p != NULL; p = p->next)

        if (viz[p->x])

            DFSt(p->x);

}

void rez()
{
    for(int i = 1 ; i <= N ; i++)
        if(!viz[i])
            DFS(i);

    for(int i = N ; i >= 1 ; i--)
        if(viz[post[i]])
        {
            nrc++;
            DFSt(post[i]);
        }
}


void afis() {

    cout << nrc << '\n';

    for (int i = 1; i <= nrc; i++) {

        for (nod* p = CTC[i]; p != NULL; p = p->next)

            cout << p->x << ' ';

        cout << '\n';

    }

}

int main()
{
    citire();

    rez();

    afis();

    return 0;
}