Aiuto Appetito aracnide (tecla)

Aiuto
1

Sto provando a risolvere Appetito aracnide ma non riesco a implementare il fatto che un nodo possa essere rivisitato. Al momento senza nodi che si ripetono (anche se so che non è corretto) questa è il mio codice:
Faccio una dfs con backtracking per trovare un ciclo dispari

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;

vector<vector<int>>V(30);
vector<int>path;
vector<bool>visit(30,false);


int dfs(int node){
	if(node==0){
		if(path.size()%2==0){ //la soluzione è pari se non contiamo il ritorno a 0

			printf("%d\n",path.size()+1);
			printf("0 ");
			
			for(auto i:path)
				printf("%d ",i);
				
			printf("0 ");
			return true;
		}
		return false;
	}
	
	
		
	visit[node]=true;
	path.push_back(node);
		
	for(auto next:V[node])
			if(dfs(next))
				return true;
	
	visit[node]=false;
	path.pop_back();
	return false;
}

int main()
{

//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);

	int N,M;
	cin>>N>>M;
	for(int i=0;i<M;i++){
		int x,y;
		cin>>x>>y;
		V[x].push_back(y);
		V[y].push_back(x);
	}
	
	
	for(auto i:V[0]){
		if(dfs(i))
			return 0;
	}

}
2

Prova a pensare in quanti modi diversi un nodo può essere utile. Se esaurisci tutti i modi non hai più bisogno di visitare di nuovo quel nodo.
Dovrebbe essere abbastanza intuitivo capire in quanti e in quali modi siccome stiamo badando alla parità della lunghezza del cammino (pari o dispari).

3

Puoi anche vedere

Appetito aracnide (tecla)

4

se incontro un nodo già visitato, controllo se ritornando su quel nodo riesco ad avere un ciclo di lunghezza dispari e cosi chiudere il ciclo

5

Ho risolto il problema così.

6

pensavo di usare le distanze, per esempio se vado su un nodo già visitato controllo se la differenza delle loro distanze(numero di archi) è dispari

7

pensavo a cio

distanza nodo che dovrebbe andare su nodo gia visitato - distanza nodo gia visitato +1 %2==1;

8

Si però poi devi anche stampare il percorso, direi che ti devi memorizzare anche i nodi che visiti.

9

mi salvo i parenti di ogni nodo ma sto trovando difficoltà
e ho un array di booleani se gia visito un nodo o no

10

L’ho fatto tempo fa e non ricordo bene ma mi sembra che basti una DFS(nodo,indice) che oltre a marcare i dati come visitati li memorizzi in un array alla posizione indice:
supponendo una cosa del genere nella sequenza dei nodi : 0,3,4,9,8,20, e che ora si torni a 9.
Bene ci siamo:
il ciclo 9,8,20,9 è dispari ed il percorso è …

11

0,3,4,9,8,20,9,4,3,0

12

Si, direi che le cose stanno così.

13

scusa ma non ho capito il perché dell’indice,intendi il percorso?

14

uso un array nodivis[] e nella DFS(nodo,indice) se nodo non è già stato visitato faccio nodivis[indice]=nodo; trovo il nodo successivo (succ) (se c’è) e chiamo DFS(succ,indice+1).

15

e se visito un nodo gia presente nell array vedo se esso ha un ciclo dispari formato dai nodi gia visitati e stampo i percorso inverso dal nodo gia visitato

16

Si puoi ma penso che, per verificare se il ciclo è di lunghezza dispari, sia più veloce tenere anche il conto delle distanze.
Anzi ho riguardato il codice e memorizzo anche quelle.

17

io avevo un vector con l attuale percorso che sto facendo,usando backtracking

18

oke, grazie mille
vedo se riesco a risolverlo

19

risolto
attuale soluzione:

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;

vector<vector<int>>V(30);
vector<int>path;
vector<int>dist(30);
vector<bool>visit(30,false);


int dfs(int node,int d){ //d sara` 1 se  dispari, 0 se pari 

	if (visit[node]) {
		if ( dist[node] != d ) {
			path.push_back(node);
			return true;
		}
		return false;
	}
		
	visit[node]=true;
	dist[node] = d;
	path.push_back(node);
	
	for(auto next:V[node])
		if(dfs(next,1-d))
			return true;
	

	path.pop_back();
	return false;
}

int main()
{

//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);

	int N,M;
	cin>>N>>M;
	for(int i=0;i<M;i++){
		int x,y;
		cin>>x>y;
		V[x].push_back(y);
		V[y].push_back(x);
	}
	
	
	dfs(0,0);

	int visitedTwice = path[path.size()-1];
	bool repeat = false;
	for (int i=path.size()-2; i >= 0; i--) {
		if ( repeat )
			path.push_back(path[i]);
		if ( path[i] == visitedTwice )
			repeat = true;
	}

	printf("%d\n",path.size()-1);
	for (int i=0; i<path.size(); i++)
		printf("%d ",path[i]);
	
	return 0;
}