014 Parcurgere DFS - componente conexe

[•danalex97]

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

[•hiticas_abel]

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

[•SebiSebi]

Foloseste o stiva exact pe principiul recursivitatii. 

[•Sapientia]

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;
}

[•classius]

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

[•alexandru70]

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.

[•sulzandrei]

Se poate rezolva si cu paduri de multimi disjuncte foarte frumos 

[•Beatrice96]

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?..

[•klamathix]

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:

Cod:

vector<vector<int>> lista(n + 1, vector<int>())

.