Territoriali 2017 Tecla 30/100

Salve. Sto provando a risolvere tecla, ma il mio codice fa solo 30/100. In due casi stamperebbe filamenti non esistenti, negli altri (sbagliati) genera un signal 9. Sinceramente, anche provando a mano alcuni casi, non capisco dov’è che il codice potrebbe sbagliare. Quello che faccio è far partire una dfs dal nodo 0, e marcare gli archi su cui passo per evitare cicli. Quando trovo un percorso valido, percorro “in catena” all’indietro le variabili dell’array dove memorizzo i precedenti, e le stampo. Allego il mio codice.

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

int n,m;
vector<int> nodi[50];
bool vis[50];
int prec[50];
int edges[50][50];
int arr;
bool flag=true;
void dfs(int k,int passi){
	
		if(!flag)return;
		
		vis[k]=true;
		for(int i=0;i<nodi[k].size()&&flag;i++){
			if(nodi[k][i]==0&&passi%2==0&&!edges[k][nodi[k][i]]){
				arr=k;
				
				flag=false;
				return;
			}
			if(!edges[k][nodi[k][i]]&&flag){
				int p=prec[nodi[k][i]];
				prec[nodi[k][i]]=k;
				
				
				edges[k][nodi[k][i]]=1;
				edges[nodi[k][i]][k]=1;
				dfs(nodi[k][i],passi+1);
				if(!flag)return;
				edges[k][nodi[k][i]]=0;
				edges[nodi[k][i]][k]=0;
				prec[nodi[k][i]]=p;
			}
		}
		
}
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b; cin>>a>>b;
		nodi[a].push_back(b);
		nodi[b].push_back(a);
	}
	for(int i=0;i<n;i++){
		vis[i]=false;
		for(int y=0;y<n;y++)edges[i][y]=false;
	}
	dfs(0,0);
	
	vector<int> perc;
	perc.push_back(0);
	while(arr!=0){
		
		perc.push_back(arr);
		arr=prec[arr];
	}
	perc.push_back(0);
	reverse(perc.begin(),perc.end());
	cout<<perc.size()-1<<endl;
	for(int i=0;i<perc.size();i++)cout<<perc[i]<<" ";

}
1 Mi Piace

Prova con

4 4
0 1
1 2
2 3
3 1

Ho provato brevemente il tuo programma e sembra dare problemi le volte in cui, come nel caso sopra, il cerchio non si chiude nell’origine. vedi Appetito aracnide (tecla)

1 Mi Piace