Program1 .campion

[•Mitza444]

Am niste intrebari la urmatoarea problema:http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=570.
1.De ce pentru testul 2 imi da 2 inloc de 1.(nu vad greseala pt. ca eu vizitez nodul 1in BF).
2.Cum pot rezolva problema altfel decat cu matrice de adiacenta??(am incercat cu o matrice bool da pica la memorie e prea mare 10000*10000,am auzit ca se poate cu ceva liste de vecini dar nu stiu sigur ce sunt).
In programul meu eu dau marchez arc intre i si i+1 daca citesc comanda "EXECUTA" si arc intre i si nr daca citesc comanda "SALT".
Dupa care fac o parcurgere BF si nodurile care raman nevizitate reprezinta instructiunile care nu se executa niciodata.

Cod:

#include<fstream>
#include<string>
#include<queue>
using namespace std;
string cmd[10001],aux;
bool graf[10001][10001],viz[10001];
int nr,rez;
queue <int> Q;
void BF(int n){
    int nod,i;
    Q.push(1);
    viz[1]=1;
    while(!Q.empty()){
        nod=Q.front();
        for(i=1;i<=n;i++){
            if(graf[nod][i] && !viz[i]){
                Q.push(i);
viz[i]=1;
            }
        }
        Q.pop();
    }
}
int main(){
int i=1,j;
ifstream f("program1.in");
f>>cmd[i];
while(cmd[i]!="."){
if(cmd[i]=="EXECUTA"){
graf[i][i+1]=1;
}
else if(cmd[i]=="SALT"){
f>>nr;
graf[i][nr]=1;
f>>aux;
if(aux=="SAU"){
f>>nr;
graf[i][nr]=1;
}
else{
i++;
cmd[i]=aux;
continue;
}
}
i++;
f>>cmd[i];
}
BF(i);
ofstream g("program1.out");
for(j=1;j<=i;j++)
if(!viz[j])
rez++;
g<<rez;
return 0;
}

[•soriyn]

Da 2 pentru ca instructiunile 5 si 7 nu se executa.E foarte ineficient sa retii graful prin matricea de adiacenta. Gandeste-te ca unele noduri pot avea doar un vecin si tu aloci memorie pentru 10000. Listele de vecini sunt niste liste care pentru fiecare nod retin vecinii acestuia. Pentru implementare poti folosi vector din stl :

Cod:

vector<int> a[10005];
//daca ai nod de la x la y faci asa, deci practic in a[x] ai toti vecinii lui x
a[x].push_back(y);
for(int i=0;i<a[j].size();i++) // si asa parcurgi toti vecinii nodului j
  int nod=a[j][i]; // a i-lea vecin al nodului j

In rest ideea ta e buna.

[•Mitza444]

Functioneaza perfect cum ai zis tu .Mersi de ajutor