[ESAME] 7 luglio 2023 es1

[Frisbon]

Che qualità ragazzi

[MarcoLinardi]

def DFS (node, G, Vis, BackEdges)
	Vis[z] = 1
	for v in G[v]
		if (Vis[v]==0)
			DFS(v)
		if (Vis[v]==1)
			BackEdges.append(z,v)
	Vis[z]=2
	return BackEdges

def Es1 (G,x,y)
	Vis = [0,...,0]
    BackEdges = []
    for node in G:
        if Vis[node] == 0:
            BackEdges = DFS(node, G, Vis, BackEdges)
	e = (x,y)
	if (e in BackEdges)
		return "YES"
	else 
		return "NO"
	return "NO"

Vis[0] = nodo non visitato
Vis[1] = nodo in visita
Vis[2] = nodo completamente visitato

[CasuFrost]

[CarloDaRomadev]

l'idea è quella di controllare se esiste un cammino da y a x

def esiste_cammino(G, y, z){
	vis = [0....0]
	vis[z] = 1
	stack.push(z)
	while stack is not empty{
		if vis[v.adiacenti[0]] == 0{
			w = v.adiacenti[0]
			if w == y{
				return true
			}
			stack.push(w)
		}
		elif v.adiacenti == []{
			stack.pop()
		}
		else{
			v.adiacenti.remove[0]
		}
	}
	return false
}

def main(G, x, y, z){
	if esiste_cammino(G, y, z) == true && esiste_cammino(G, x, y) == true{
		return 'YES'
	}
	else{
		return false
	}
}

// costo = O(n+m)

Dimostrazione correttezza:
Sappiamo per ipotesi che esiste un cammino da x a y (x,y), (x,y) è un arco all'indietro solo se esiste un cammino dove apro y prima di x e lo chiudo dopo di x cioè se t[y] < t[x] && T[y] >= T[x]. se ho un cammino da y a x, l'arco (x,y) risulterà superfluo, non sarà contenuto nell'albero di visita e sarà all'indietro

[CarloDaRomadev]

//[ESAME] 7 luglio 2023 es1 #75
def check(G,x,vis): {
	vis[x] = 1
	for w in x.adiacenti{
		if vis[w] == 0{
			check(G,w,vis)
		}
	}
}
def aux(G,x){
	check(G,x,vis)
	if vis[y] == 1{
		return yes
	}
	else{
		return nope
	}
}