1. 🌌 Wormholes – Poduri prin spațiu și timp

## Ce sunt wormholes?

Un wormhole (în română: „gaură de vierme”) este un concept teoretic din fizică ce descrie un tunel prin spațiu-timp care ar putea conecta două puncte foarte îndepărtate din Univers.

Ideea apare din ecuațiile teoriei relativității generale formulate de Albert Einstein. În 1935, el și Nathan Rosen au descris o structură numită „pod Einstein-Rosen”, considerată primul model teoretic de wormhole.

—-

## 🌀 Cum ar arăta un wormhole?





Un wormhole este adesea reprezentat ca:

• Două „guri” situate în puncte diferite din spațiu
• Un tunel care le conectează
• O scurtătură între două regiuni foarte îndepărtate

Dacă Universul ar fi o foaie de hârtie, un wormhole ar fi ca și cum ai îndoi foaia și ai face o gaură direct între două puncte.

—-

## 🔬 Există wormholes în realitate?

Până în prezent:

• Nu au fost observați direct
• Sunt doar soluții matematice ale ecuațiilor
• Ar necesita „materie exotică” pentru a rămâne stabili

Unii cercetători cred că la nivel cuantic ar putea exista micro-wormholes extrem de mici, dar nu există dovezi experimentale clare.

—-

## 🚀 Wormholes în filme și cultură

Conceptul a devenit popular în literatura și filmele SF, unde este folosit pentru călătorii interstelare rapide.

Un exemplu celebru este filmul Interstellar, unde un wormhole permite explorarea altor galaxii.

—-

## 🧠 Sunt posibile călătoriile în timp?

Teoretic, unele modele sugerează că wormholes ar putea permite și deplasarea în timp, nu doar în spațiu. Totuși:

• Ar apărea paradoxuri (ex: paradoxul bunicului)
• Stabilitatea ar fi extrem de dificilă
• Energia necesară ar fi uriașă

Deocamdată, rămân doar o ipoteză fascinantă.

—-

## ✨ Concluzie

Wormholes reprezintă una dintre cele mai interesante idei din fizica teoretică. Deși nu știm dacă există cu adevărat, ele ne ajută să explorăm limitele cunoașterii despre Univers, spațiu și timp.

Poate într-o zi, ceea ce azi pare science-fiction va deveni realitate. 🌠

Rețea de Orașe – Problemă Completă de Grafuri

Această problemă combină trei concepte fundamentale din teoria grafurilor: arbori de acoperire minimi, drumuri minime și componente conexe. Este o problemă complexă care testează înțelegerea profundă a algoritmilor pe grafuri și capacitatea de a combina soluții diferite pentru a rezolva cerințe multiple.

Descrierea Problemei

Considerăm o rețea de transport formată din N orașe conectate prin M drumuri bidirecționale. Fiecare drum are două atribute importante: o lungime (relevantă pentru distanțe) și un cost de întreținere (relevant pentru construcția rețelei).

Guvernul dorește să optimizeze rețeaua de transport urmând trei obiective distincte:

• Construirea unei rețele de cost minim care conectează toate orașele
• Respectarea unei constrângeri de grad maxim K pentru fiecare oraș
• Calcularea distanțelor minime între orașe importante
• Analiza robusteței rețelei prin eliminarea drumurilor scumpe
  

Cerințe Detaliate

1. Arbore de Acoperire Minim cu Constrângere de Grad

Primul obiectiv este să construim un arbore de acoperire (MST – Minimum Spanning Tree) cu cost total minim, dar cu o constrângere suplimentară: fiecare oraș poate avea cel mult K drumuri directe în rețeaua finală.

Această constrângere transformă problema clasică MST într-o variantă mai complexă care necesită algoritmi modificați.

2. Distanțe Minime – Algoritmul Dijkstra

Al doilea obiectiv este să calculăm distanța minimă între două orașe date folosind lungimile drumurilor. Aceasta este o aplicație clasică a algoritmului Dijkstra pe grafuri ponderate.

3. Componente Conexe – Disjoint Set Union

Al treilea obiectiv analizează robustețea rețelei prin eliminarea tuturor drumurilor cu cost de întreținere mai mare decât o valoare X. Trebuie să determinăm câte componente conexe rămân în rețeaua rezultată.

Algoritmi și Structuri de Date

Algoritmul Kruskal Modificat

Pentru prima cerință, folosim o variantă modificată a algoritmului Kruskal:

1. Sortăm toate muchiile după cost crescător
2. Iterăm prin muchiile sortate
3. Pentru fiecare muchie (u, v):
   - Verificăm dacă u și v sunt în componente diferite
   - Verificăm dacă grad[u] < K și grad[v] < K
   - Dacă ambele condiții sunt true:
     * Adăugăm muchia în MST
     * Unim componentele (DSU)
     * Incrementăm gradele

Complexitate: O(M log M) pentru sortare + O(M α(N)) pentru DSU

Algoritmul Dijkstra

Pentru distanțe minime, implementăm Dijkstra standard:

1. Inițializăm distanțe cu infinit
2. Setăm dist[sursa] = 0
3. Folosim un min-heap (nod, distanță)
4. Extragem nodul cu distanță minimă
5. Relaxăm muchiile adiacente
6. Repetăm până ajungem la destinație

Complexitate: O(M log N) folosind priority queue

Disjoint Set Union (DSU)

Pentru componente conexe, folosim DSU cu optimizări:

class DSU:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def unite(self, a, b): a, b = self.find(a), self.find(b) if a b: return False if self.rank[a] < self.rank[b]: a, b = b, a self.parent[b] = a if self.rank[a] self.rank[b]: self.rank[a] += 1 return True

Complexitate: O(M α(N)) unde α este funcția inversă Ackermann

Implementare în C++

Structuri de Date

struct Edge {
    int to, cost, length;
    bool operator<(const Edge& other) const {
        return cost > other.cost; // pentru min-heap
    }
};

class DSU {
private: vector parent, rank;
public: DSU { /* inițializare */ } int find(int x) { /* path compression */ } bool unite(int a, int b) { /* union by rank */ }
};

Funcția Principală

Funcția main() orchestrează cele trei etape:

int main() {
    // Citire date
    // 1. MST cu constrângere de grad
    // 2. Dijkstra pentru distanțe
    // 3. DSU pentru componente conexe
    // Afișare rezultate
}

Implementare în Python

Avantajele Python

Python oferă o sintaxă mai concisă și biblioteci integrate pentru structuri de date complexe:

import heapq  # pentru priority queue
from collections import defaultdict

1. Citire mai elegantă
   N, M, K, Q, X = map(int, fin.readline().split())

1. DSU implementat ca o clasă
   class DSU: def __init__(self, n): pass def find(self, x): pass def unite(self, a, b): pass

Analiza Complexității

Timp de Execuție

MST modificat: O(M log M) – dominat de sortare
Dijkstra: O(M log N) – eficient pentru grafuri rare
Componente conexe: O(M α(N)) – aproape liniar

Total: O(M log M + M log N) – acceptabil pentru constrângerile date

Memorie Utilizată

Graf: O(N + M) – listă de adiacență
DSU: O(N) – vectori parent și rank
Muchii: O(M) – pentru sortare și procesare

Total: O(N + M) – optim pentru N, M ≤ 10000

Testare și Validare

Caz de Test

Input:
6 9 3 2 50
1 2 10 20
1 3 15 30
2 4 25 60
3 5 30 45
4 6 40 70
5 6 45 65
1 6

Output:
185 # Cost MST cu grad ≤ 3
75 # Distanța minimă 1→6
2 # Componente conexe după eliminare cost > 50

Verificare Manuală

MST: Muchiile (1,2,20), (1,3,30), (2,4,60), (3,5,45), (4,6,70) = 225
Dijkstra: Drumul 1→2→4→6 = 10+25+40 = 75
Componente: Eliminăm muchiile cu cost > 50, rămân 2 componente

Extensii și Optimizări

Posibile Îmbunătățiri

Algoritmi alternativi: Prim modificat pentru MST cu constrângeri
Optimizări: Early termination în Dijkstra când ajungem la destinație
Paralelizare: Procesare paralelă a componentelor conexe

Aplicații Reale

Rețele de comunicare: Design de rețele cu constrângeri de grad
Transport urban: Planificare rute optime
Infrastructură: Analiza robusteței rețelelor critice

Concluzii

Această problemă demonstrează importanța combinării mai multor algoritmi de grafuri pentru a rezolva probleme complexe din lumea reală. Constrângerile suplimentare fac problema mai interesantă și mai apropiată de scenariile practice unde resursele sunt limitate.

Soluția prezentată este eficientă și scalabilă, putând gestiona rețele de dimensiuni moderate cu performanțe bune atât în C++ cât și în Python.

Lecții Învățate

• Combinația de algoritmi: Problemele reale necesită adesea combinații de algoritmi
• Constrângeri: Constrângerile pot transforma probleme standard în variante complexe
• Flexibilitate: Alegerea limbajului potrivit poate simplifica implementarea
• Testare: Validarea cu cazuri de test este esențială pentru corectitudine