Cod sursa(job #1992170)

Utilizator infomaxInfomax infomax Data 19 iunie 2017 19:04:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <cstring>
#include <stack>

using namespace std;

ifstream F("ctc.in");
ofstream G("ctc.out");

int v[100003], n, m, K, k, w[100003], x, y, idx[100003], ll[100003], t = 1;
struct node{int info; node *urm;} *L[100002], *l[100003], *q;
stack <int> s;

void dfs(int nod)
{
    v[nod] = 1;
    s.push(nod);
    node *p;
    p = L[nod]->urm;
    idx[nod] = ll[nod] = t;
    t ++;
    while(p != NULL)
    {
        if(!idx[p->info]) dfs(p->info), ll[nod] = min(ll[p->info], ll[nod]);
        else if(v[p->info]) ll[nod] = min(ll[p->info], ll[nod]);
        p=p->urm;
    }
    if(idx[nod] == ll[nod])
    {
        ++ K;
        do
        {
            q = new node;
            q->urm = l[K]->urm;
            x = s.top();
            q->info = x;
            s.pop();
            v[x] = 0;
            l[K]->urm = q;
        }while(x != nod);
    }
}

int main()
{
    F >> n >> m;
    for(int i = 1; i <= n; ++ i)
        L[i] = new node, L[i]->urm = NULL;
    for(int i = 0; i < m; ++ i)
    {
        F >> x >> y;
        q = new node;
        q->urm = L[x]->urm;
        q->info = y;
        L[x]->urm = q;
    }

    for(int i = 1; i <= n; ++ i)
        l[i] = new node, l[i]->urm = NULL;
    for(int i = 1; i <= n; ++ i)
        if(!idx[i]) dfs(i);
    G << K<< '\n';
    for(int i = 1; i <= K; ++ i)
    {
        q = l[i]->urm;
        while(q != NULL)
        {
            G << q->info << " ";
            q=q->urm;
        }
        G << '\n';
    }
    return 0;
}