Merge branch 'main' into main

mhayter · web-flow · commit a990b25979f2 · 2025-04-16T06:37:51.000-04:00
diff --git a/src/graph/finding-negative-cycle-in-graph.md b/src/graph/finding-negative-cycle-in-graph.md
@@ -30,50 +30,47 @@ Do $N$ iterations of Bellman-Ford algorithm. If there were no changes on the las
 struct Edge {
     int a, b, cost;
 };
-
-int n, m;
+ 
+int n;
 vector<Edge> edges;
 const int INF = 1000000000;
-
+ 
 void solve() {
-    vector<int> d(n, INF);
+    vector<int> d(n, 0);
     vector<int> p(n, -1);
     int x;
-    
-    d[0] = 0;
-
+ 
     for (int i = 0; i < n; ++i) {
         x = -1;
         for (Edge e : edges) {
-            if (d[e.a] < INF && d[e.a] + e.cost < d[e.b]) {
+            if (d[e.a] + e.cost < d[e.b]) {
                 d[e.b] = max(-INF, d[e.a] + e.cost);
                 p[e.b] = e.a;
                 x = e.b;
             }
         }
     }
-
+ 
     if (x == -1) {
         cout << "No negative cycle found.";
     } else {
         for (int i = 0; i < n; ++i)
             x = p[x];
-
+ 
         vector<int> cycle;
         for (int v = x;; v = p[v]) {
             cycle.push_back(v);
             if (v == x && cycle.size() > 1)
                 break;
         }
         reverse(cycle.begin(), cycle.end());
-
+ 
         cout << "Negative cycle: ";
         for (int v : cycle)
             cout << v << ' ';
         cout << endl;
     }
 }
-
 ```
 
 ## Using Floyd-Warshall algorithm
diff --git a/src/sequences/k-th.md b/src/sequences/k-th.md
@@ -68,7 +68,7 @@ T order_statistics (std::vector<T> a, unsigned n, unsigned k)
 
 ## Notes
 * The randomized algorithm above is named [quickselect](https://en.wikipedia.org/wiki/Quickselect). You should do random shuffle on $A$ before calling it or use a random element as a barrier for it to run properly. There are also deterministic algorithms that solve the specified problem in linear time, such as [median of medians](https://en.wikipedia.org/wiki/Median_of_medians).
-* A deterministic linear solution is implemented in C++ standard library as [std::nth_element](https://en.cppreference.com/w/cpp/algorithm/nth_element).
+* [std::nth_element](https://en.cppreference.com/w/cpp/algorithm/nth_element) solves this in C++ but gcc's implementation runs in worst case $O(n \log n )$ time.
 * Finding $K$ smallest elements can be reduced to finding $K$-th element with a linear overhead, as they're exactly the elements that are smaller than $K$-th.
 
 ## Practice Problems
