Cod sursa(job #2651411)

Utilizator Arina2003Arina Aioanei Arina2003 Data 22 septembrie 2020 16:28:52
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>

using namespace std;

const int NMAX = 100000;

struct nod
{
    int x;
    nod *next;
};

nod *G[NMAX + 1],   ///lista vecinilor, graf initial
    *GT[NMAX + 1],  ///lista vecinilor, graf transpus
    *CTC[NMAX + 1]; ///lista nodurilor componentei tare conexe

int n,m,nrc,
    nr,post[NMAX + 1];

bool viz[NMAX + 1];

ifstream f("ctc.in");
ofstream g("ctc.out");

void add(nod *&cap_1st,int nod_ad)
{
    nod *p;
    p = new nod;
    p -> x = nod_ad;
    p -> next = cap_1st;
    cap_1st = p;
}

void citireGraf()
{
    int x,y;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        add(G[x],y);///adaug arc in G
        add(GT[y],x);///adaug arc in GT
    }
}

void DFS(int vf)///Determinam toate nodurile in care se poate ajunge din vf
{
    viz[vf] = 1;   ///+
    for(nod *p = G[vf]; p != NULL; p = p -> next)
        if(viz[p->x] == 0)
            DFS(p->x);
    post[++nr] = vf;///se memoreaza ordinea de parcurgere a nodurilor(postordine)
}

void componente()  ///Algoritmul Kosaraju-Sharir
{
    for(int i=1;i<=n;i++)
        if(viz[i] == 0)
            DFS(i);         ///DFS pe graful initial
    //
    for(int i=n;i>=1;i--)       ///se parcurg nodurile in postordine
        if(viz[post[i]] == 1)   ///nodul post[i] nu a fost plasat intr-o CTC
        {
            nrc++;
            DFS(post[i]);       ///DFS pe graful transpus
        }
}

void afis()
{
    g<<nrc<<'\n';
    for(int i=1;i<=nrc;i++)
    {
        for(nod *p = CTC[i]; p!=NULL; p = p -> next)
            g<< p->x <<' ';
        g<<'\n';
    }
}
int main()
{
    citireGraf();
    componente();
    afis();
    return 0;
}