Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 027 Componente tare conexe  (Citit de 7137 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
filipb
Vorbaret
****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« : Decembrie 24, 2008, 13:12:42 »

Aici puteti discuta despre problema Componente tare conexe.
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #1 : Mai 28, 2010, 17:20:27 »

Edit:
Am gasit greseala. Ms mult de ajutor. Ok
« Ultima modificare: Mai 28, 2010, 20:59:25 de către Trimbitas Petru » Memorat
alexandru92
Vorbaret
****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #2 : Mai 28, 2010, 17:30:22 »

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


Karma: 0
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #3 : Decembrie 13, 2010, 09:55:30 »

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!
« Ultima modificare: Decembrie 13, 2010, 11:52:08 de către Gabriel Bitis » Memorat
livium
Strain


Karma: -2
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #4 : Decembrie 13, 2010, 20:44:46 »

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?
Memorat
toni2007
Vorbaret
****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #5 : Decembrie 13, 2010, 21:24:11 »

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.
Memorat
newsabbath
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #6 : Decembrie 13, 2010, 22:56:24 »

Buna,

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


Multumesc!
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« Răspunde #7 : Decembrie 16, 2010, 22:53:58 »

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 Sad)
Memorat
newsabbath
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #8 : Decembrie 21, 2010, 01:12:26 »

multumesc

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

sabbath
Memorat
maritim
Vorbaret
****

Karma: 59
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #9 : Octombrie 11, 2011, 17:54:13 »

Eroare in evaluator Sad .
Memorat
mihaibogdan10
Strain


Karma: -1
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #10 : Noiembrie 04, 2011, 23:30:42 »

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...
Memorat
valentin.harsan
Strain
*

Karma: 33
Deconectat Deconectat

Mesaje: 41



Vezi Profilul
« Răspunde #11 : Noiembrie 08, 2011, 11:09:49 »

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
Memorat
claudiumihail
Strain
*

Karma: 5
Deconectat Deconectat

Mesaje: 33



Vezi Profilul
« Răspunde #12 : Ianuarie 15, 2012, 08:36:45 »

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
Memorat
CosminRusu
De-al casei
***

Karma: 77
Deconectat Deconectat

Mesaje: 104



Vezi Profilul
« Răspunde #13 : Mai 25, 2016, 22:03:32 »

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.
Memorat
AlexandruValeanu
Vorbaret
****

Karma: 29
Deconectat Deconectat

Mesaje: 167



Vezi Profilul
« Răspunde #14 : Mai 25, 2016, 23:34:12 »

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.
Memorat
CosminRusu
De-al casei
***

Karma: 77
Deconectat Deconectat

Mesaje: 104



Vezi Profilul
« Răspunde #15 : Mai 26, 2016, 09:52:22 »

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?
Memorat
tudorgalatan
Strain
*

Karma: -1
Deconectat Deconectat

Mesaje: 27



Vezi Profilul
« Răspunde #16 : August 12, 2016, 10:48:26 »

OUTPUT:

Cod:
4
4 5 10 6
8
2 3
1 7 9
Memorat
st_marian
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #17 : Aprilie 30, 2019, 16:01:08 »

...
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines