Imprimă pagina - 027 Componente tare conexe

Titlul: 027 Componente tare conexe
Scris de: Filip Cristian Buruiana din Decembrie 24, 2008, 13:12:42

Aici puteti discuta despre problema Componente tare conexe (http://infoarena.ro/problema/ctc).

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Petru Trimbitas din Mai 28, 2010, 17:20:27

Edit:
Am gasit greseala. Ms mult de ajutor. :ok:

Titlul: Răspuns: 027 Componente tare conexe
Scris de: alexandru din Mai 28, 2010, 17:30:22

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

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Caraman Sabina din 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!

Titlul: Răspuns: 027 Componente tare conexe
Scris de: livica din 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?

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Pripoae Teodor Anton din 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.

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Caraman Sabina din Decembrie 13, 2010, 22:56:24

Buna,

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

Multumesc!

Titlul: Răspuns: 027 Componente tare conexe
Scris de: George Marcus din 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 :()

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Caraman Sabina din Decembrie 21, 2010, 01:12:26

multumesc

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

sabbath

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Cristian Lambru din Octombrie 11, 2011, 17:54:13

Eroare in evaluator :( .

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Mihai Bogdan din 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...

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Valentin Harsan din 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

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Claudiu Mihail din 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 (http://en.wikipedia.org/wiki/Cheriyan%E2%80%93Mehlhorn/Gabow_algorithm)), care ia 100p (vezi http://infoarena.ro/job_detail/661763 (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

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Cosmin Rusu din 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 (https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm.), iar in articolul asta (http://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/) chiar insista pe aceasta greseala.
Sunt curios daca ar trebui imbunatatite testele sau pur si simplu modificarea asta nu afecteaza neaparat corectitudinea algoritmului.

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Alexandru Valeanu din Mai 25, 2016, 23:34:12

Implementare propusa de R. Sedgewick (http://algs4.cs.princeton.edu/42digraph/TarjanSCC.java.html (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.

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Cosmin Rusu din 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?

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Roman Tudor din August 12, 2016, 10:48:26

OUTPUT:

Cod:

Titlul: Răspuns: 027 Componente tare conexe
Scris de: Stoica Marian din Aprilie 30, 2019, 16:01:08

...

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva educationala => Subiect creat de: Filip Cristian Buruiana din Decembrie 24, 2008, 13:12:42