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