infoarena

Aici puteti discuta despre problema Parcurgere DFS - componente conexe (http://infoarena.ro/problema/dfs).

de ce la testul 17 e raspuns 2?

Pai o explicatie stiintifica nu pot sa'ti dau, dar daca s'au luat punctaje de 100, pe aceleasi teste pe care ai luat tu 95, inseamna ca la testul 17 chiar sunt 2 componente conexe, de'aia raspunsul e 2.
Componentele sunt fomate din nodurile de la 1 la 99997 respectiv de la 99998 la 100000.

oricum testul 17 e gresit:
sunt 100000 de muchii,iar fisierul de intrare are 99999

Am modificat testul 17 si am reevaluat :).

Am si eu o intrebare... stiu ca e putin ciudata, da' limba romana nu e punctu' meu forte :D Ce inseamna componente conexe? :D

O componenta conexa intr-un graf neorientat este o submultime maximala C a multimii de noduri astfel incat oricare ar fi doua noduri x si y din C, exista drum de la x la y si de la y la x.
Google it. In plus, uita-te pe sursele din arhiva si ai sa vezi cum functioneaza algoritmul de determinare a componentelor astea.

Mersi fain. Am inteles :)

Este DFS mai rapid decat BFS :?, sau este numai legat de testele acestea? cu al doilea am luat 60 de puncte.

DFS are aceeasi complexitate cu BFS: O(n+m).

E adevarat, doar ca una este recursiva iar cealalta iterativa, de aici diferenta de timp. Probabil ca ai folosit STL la bfs, care merge mai incet ca stiva (sa ma corecteze cineva daca gresesc), sau la bfs ai bagat de mai multe ori nodurile in coada :),

Se poate DFS si iterativ. Si ma chinui acum sa il implementez, dar nu am alte idei decat sa imi creez o stiva care sa o inlocuiasca pe cea din sistem pt functii. A facut careva interativ DFS?

Pai altfel nu ai cum.  :) Iti retii in stiva nodurile, in ordinea parcurgerii. Atunci cand nu mai ai unde sa mergi din nodul st[vf], stergi varful stivei (--vf), si incerci noul varf (ii parcurgi vecinii). Repeti procedeul pana cand stiva devine vida. Uite un pseudocod:

Implementarea e simpla! Succes!

am facut-o cu liste si merge viss... :banana:

Merge si recursiv ,sursa  oficiala  e facuta recursiv ;)

Postul tau e cam degeaba.  :) Daca ai fi citit cu atentie, ti-ai fi dat seama ca ma refeream la cum poate sa faca iterativ. Adica sa transforme algoritmul recursiv in iterativ, prin simularea stivei. Prin "altfel nu ai cum" ma refeream la faptul ca simularea stivei e obligatorie pentru a face iterativ.

Eu am facut cu matrice de adiacenta si am luat 100. :)

Tu ai liste de vecini, nu matrice de adiacenta.
Matricea de adiacenta e o matrice A de dimensiune N x N, unde A[ i ][ j ] = 1 daca exista muchie de la nodul i la nodul j, sau A[ i ][ j ] = 0 in caz contrar.

Eu iau de la testu 12-20 - Killed by signal 11. :-? imi poate spune cnv unde e 'problema' pe solutia trimisa?

Vezi ca limita e 1 <= N <= 100 000 !!! (tu ai declarat vectorii de 10 005 )

imi poate spune cineva, va rog, ce inseamna eroarea "Non-zero exit status." in borderoul de evaluare ?  :?
multumesc..

Tu ai declarat o matrice [0..100,0..100], deci dupa ce citesti (de exemplu) 101 incerci sa accesezi o zona de memorie nealocata.
Va trebui sa retii matricea sub forma de liste de adiacenta.

salutare!...
am si eu o problema...trimit sursa si iau doar 15 pct:-? si pe restul testelor "incorect"...dar oricate teste as da eu...imi da ok! daca are cineva timp sa se uite pe sursa...poate vede greseala pe care nu o vad eu:-?
adresa e: http://infoarena.ro/job_detail/544998 (http://infoarena.ro/job_detail/544998)


am rezolvat...multumesc oricum :peacefingers:

 Nu posta consecutiv pe aceeasi tema. Editeaza-ti mesajele anterioare!

Si ... de unde as putea invata cum se lucreaza cu pointeri ?

http://zanasi.chem.unisa.it/download/C.pdf -> aceasta carte contine tot ce iti trebuie despre limbajul C. Capitolul 5 este dedicat pointerilor   :)
Vezi ca la problema asta poti sa eviti folosirea pointerilor. Iti poti tine un vector din stl cu vecinii fiecarui nod  :wink:

Multumesc frumos.  :ok: Stiu ca se poate fara ( am si facut fara  :) ) , insa din intamplare am observat ca sursa oficiala e cu pointeri.

Cum as putea simula recursivitatea cu ajutorul unei structuri de date?

Foloseste o stiva exact pe principiul recursivitatii.  :ok:

Algoritmul este exact acelasi cu sursa de 50 de puncte...si totusi primesc doar 5 :)...ma poate lamuri cineva? ](*,),Am incercat sa implementez si listele de adiacenta si primesc doar 10 puncte..
#include <iostream>
#include <cstdio>
#define Nmax 1001
using namespace std;
int n,i,j,cmp=0;
int a[Nmax][Nmax];
bool viz[Nmax];
void citire(int &n)
{
    int m;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&n,&m);
    int x,y;
    for(i=1;i<=m;++i)
    {
        scanf("%d %d",&x,&y);
        a

• [y]=1;

        a[y]

• =1;

    }
}
void dfs(int x)
{
    viz

• =1;

    for(i=1;i<=n;++i)
     if (!viz && a

• ) dfs(i);

}
int main()
{
    citire(n);
    for(i=1;i<=n;++i)
     if (!viz) {++cmp;dfs(i);}
    printf("%d",cmp);
    return 0;
}

Nu mai folosi variabile globale, daca nu stii cum sa le administrezi. Variabila "i" va fi folosita si in functia main si in functia dfs.
Pentru testul 3 0 programul tau da 1 cand ar trebui sa dea 3

Imi poate spune si mie cineva ce probleme ar trebui sa rezolv pentru a consolida grafurile? Pana acum stiu bfs si dfs, si am inteles cat de cat floyd-warshall.

Se poate rezolva si cu paduri de multimi disjuncte foarte frumos  :ok:

Imi poate explica si mie cineva de ce imi da doar 5 pct la programul asta:

#include<iostream>
#include<fstream>
#include<vector>
#include<map>
using namespace std;

pair<int, int> P;
vector<pair<int, int> > v;

map<int, vector<int> > lista;

int n,m,a,b, viz[100];

void citire()
{
    ifstream f("dfs.in");
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        lista[a].push_back(b);
        lista.push_back(a);
    }
}

void df(int nod)
{
    viz[nod]=1;
    for(int i=0;i<lista[nod].size();i++)
        if(viz[lista[nod]]==0)
            df(lista[nod]);
}

int comp_conex()
{
    int k=0;
    for(int i=1;i<=n;i++)
    {
        if(viz==0)
        {
            df(i);
            k++;
        }
    }
    return k;
}

int main()
{
    ofstream g("dfs.out");
    citire();
    g<<comp_conex();
}

Raspunsul e corect..oare nu accepta implementarea cu map, vector, pair?..

Salut! Vectorul tău viz[] este mult prea mic pentru datele de intrare.
Apropo, n-ai niciun motiv să folosești map la problema asta. Poți să declari lista așa:
.