027 Componente tare conexe

[•filipb]

Aici puteti discuta despre problema Componente tare conexe.

[•S7012MY]

Edit:
Am gasit greseala. Ms mult de ajutor.

[•alexandru92]

Cand  extragi din stiva elementele nod nu trebuie sa fie diferit de z, nu de n ?

[•newsabbath]

Buna

Va rog cine are timp... Am nevoie de ajutor.

Cod:

#include <fstream>
#include <stdio.h>
#include <stack>

using namespace std;

struct nod
{
    int inf;
    nod *urm;
}*L[100000];



int n,m;
int viz[100001], low[100001], in, vizs[100001];
stack <int> S;

void add(nod *&prim, int vec)
{
    nod *p= new nod;
    p->inf = vec;
    p->urm = prim;
    prim = p;
}



void citire()
{

    scanf("%d %d",&n,&m);

    for (int i = 0; i < m; i++)
   {
        int x,y;
        scanf("%d %d",&x,&y);
        add(L[x], y);
    }
}

void tarjan(int v)//indicele nodului din care plec
{
    viz[v] = in;
    low[v] = in;
    in++;
    S.push(v);
    vizs[v] = 1;
    for(nod *p=L[v]; p; p=p->urm)
        if(viz[p->inf] == 0)
            {
                tarjan(p->inf);
                low[v] = min(low[v], low[p->inf]);
            }
        else
            if(vizs[p->inf] == 1)
                low[v] = min(low[v], viz[p->inf]);

 int x;
    if(viz[v] == low[v])
    do
    {
        x = S.top();
        printf("%d ", x);
        vizs[x] = 0;
        S.pop();
    }while(v != x );


}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    citire();
    for(int i=1;i<=n;i++)
        if(viz[ i ] == 0)
        {
            tarjan(i);
            printf("\n");
        }
    return 0;
}

Multumesc frumos!

[•livium]

Am trimis si eu un program spre evaluare (algoritmul lui Gabow) si am erorile astea pe care nu le-am avut pe pc-ul meu:

Eroare de compilare:
user.cpp:160:2: warning: no newline at end of file
user.cpp:30: error: '>>' should be '> >' within a nested template argument list
user.cpp:31: error: '>>' should be '> >' within a nested template argument list
user.cpp:71: error: '>>' should be '> >' within a nested template argument list
    

Care-i faza?

[•toni2007]

Nu trebuie sa apara doua semne ">" unul langa altul, pt ca se considera operatorul de shift-are. Pune cu un spatiu intre ele cand declari containeri stl.

[•newsabbath]

Buna,

va uitati peste alg tarjan ...
astept o idee
Sursa este mai sus.


Multumesc!

[•PlayLikeNeverB4]

Din cate am observat, problema ta e la afisare.

Cod:

    for(int i=1;i<=n;i++)
        if(viz[ i ] == 0)
        {
            tarjan(i);
            printf("\n");
        }

In codul de mai sus, se executa "printf("\n");" doar cand se trece la alta componenta conexa (pentru ca altfel se merge pe lantul de vecinatati in interiorul procedurii).
De asemenea, trebuie sa afisezi si numarul de componente tari conexe, deci trebuie sa retii toate componentele pentru a le afisa dupa ce afisezi numarul lor.
De aici probabil stii ce ai de facut.
Sper ca te-am ajutat. (Mie nu mi-a verificat nimeni sursele )

[•newsabbath]

multumesc

si eu sper sa apuc ziua sa nu mai fie nevoie ...

sabbath

[•maritim]

Eroare in evaluator .

[•mihaibogdan10]

S-a modificat de curant limita superioara de timp? Acum e 0,05s.
Am trimis pana si solutia oficiala pentru 100 de puncte si iese din timp la trei teste.

Am observat ca acum ceva vreme lumea trecea teste cu 0.3s > 0.05s lejer...

[•valentin.harsan]

mda... se pare ca acu nu poti lua mai mult de 60 pct. la multe probleme nu se mai poate lua 100 odata cu injumatatirea timpului

[•claudiumihail]

Salut,

Ar merita mentionat in descrierile solutiilot posibile pentru gasirea componentelor tare conexe si algoritmul Cheriyan–Mehlhorn/Gabow (http://en.wikipedia.org/wiki/Cheriyan%E2%80%93Mehlhorn/Gabow_algorithm), care ia 100p (vezi http://infoarena.ro/job_detail/661763) si se comporta ca timpi cam la fel cu algoritmul lui Tarjan. Implementation-wise pare putin mai straight forward decat algoritmul lui Tarjan (nu ca al lui Tarjan ar fi extrem de complicat).

Anyway just my 2 cents. Poate foloseste cuiva sa stie si de alternativa asta.

Claudiu

[•CosminRusu]

Mi se pare ca solutia oficiala care implementeaza algoritmul lui Tarjan nu e chiar corecta. Cel putin in cazul doi cand avem o muchie inapoi,

Cod:

low[node] = min(low[node], idx[new_node]); 
si nu 
low[node] = min(low[node], low[new_node]); 

intrucat low[node] ar trebui sa fie indicele minim pe care il putem atinge printr-o singura muchie inapoi.
Asa vad ca e implementat pe wikipedia, iar in articolul asta chiar insista pe aceasta greseala.
Sunt curios daca ar trebui imbunatatite testele sau pur si simplu modificarea asta nu afecteaza neaparat corectitudinea algoritmului.

[•AlexandruValeanu]

Implementare propusa de R. Sedgewick (http://algs4.cs.princeton.edu/42digraph/TarjanSCC.java.html) foloseste varianta de pe Infoarena.
Este clar o sursa mult mai buna si mai de incredere decat articolul de pe geeksforgeeks.

[•CosminRusu]

Am gasit o explicatie foarte buna aici: http://stackoverflow.com/questions/16250337/about-tarjans-algorithm-for-finding-scc.
Implementarea pe care ai dat-o e interesanta pentru ca nu verifica daca nodul e in stiva cand ia minimul, de ce functioneaza?

[•tudorgalatan]

OUTPUT:

Cod:

4
4 5 10 6 
8 
2 3 
1 7 9 

[•st_marian]

...