Cod sursa(job #2132488)

Utilizator NannyiMaslinca Alecsandru Mihai Nannyi Data 15 februarie 2018 20:03:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <cstdio>
#include <vector>
#define nmax 100005
using namespace std;

FILE *f=fopen("ctc.in","r");
FILE *g=fopen("ctc.out","w");

vector<int>Q[nmax],Stk,componente[nmax];

int n,m,indexes[nmax],index,lowest[nmax],nrcomponente;
bool instk[nmax];

void read()
{
    fscanf(f,"%d %d",&n,&m);
    for (int i=1; i<=m; ++i)
    {
        int a,b;
        fscanf(f,"%d %d",&a,&b);
        Q[a].push_back(b);
    }
}

void tarjan(int nod)
{
    indexes[nod]=++index;
    lowest[nod]=index;
    Stk.push_back(nod);
    instk[nod]=true;
    for (auto w:Q[nod])
    {
        if (!indexes[w]) // parcurgem nodurile nevizitate
        {
            tarjan(w);
            lowest[nod]=min(lowest[nod],lowest[w]);
        }
        else if (instk[w])
        {
            lowest[nod]=min(lowest[nod],indexes[w]);
            // daca e in stack <=> nu face parte dintr-o ctc inca
            // e o muchie de intoarcere deci
            // altfel, face parte dintr-o ctc deja
        }
    }
    if (lowest[nod]==indexes[nod])  //avem parintele componentei tare conexe
    {
        int curent;
        ++nrcomponente;
        do
        {
            curent=Stk.back();
            Stk.pop_back();
            instk[curent]=false;
            componente[nrcomponente].push_back(curent);
        }
        while (curent!=nod);
    }
}

void afis()
{
    fprintf(g,"%d\n",nrcomponente);
    for (int i=1;i<=nrcomponente;++i)
        {for (auto w:componente[i])
            fprintf(g,"%d ",w);
        fprintf(g,"\n");}
}

void solve()
{
    for (int i=1; i<=n; ++i)
        if (!indexes[i])
            tarjan(i);
}

int main()
{
    read();
    solve();
    afis();
    return 0;
}