A - Increment or Smash Strategy: Direct simulation. Every element that is not the global maximum will undergo a reset to zero followed by an increment, contributing exactly two steps to the total. However, identical values only incur this penalty once. The global maximum avoids the reset step altoge...
A. [POI2004] SZP Description Given a directed graph with cycles, where each node has exactly one outgoing edge (non-self-loop), select the maximum number of nodes such that every selected node has at least one immediate predecessor that is not selected. Solution Observe that each weakly connected co...
1. Topological Sorting Definition: Let $G = (V, E)$ be a directed graph with $n$ vertices. A vertex sequence from $V$ is called a topological sequence if and only if: for any path from vertex $u$ to $v$, $u$ appears before $v$ in the sequence. Basic Idea: Select a vertex with no predecessors (in-deg...
You are given numCourses labeled from 0 to numCourses - 1 and a list of prerequisite pairs prerequisites where prerequisites[i] = [a, b] means that course a depends on course b (i.e., b must be taken before a). Determine if its possible to finish all courses, that is, whether the dependency graph co...
Topological Sorting Kahn's Algorithm import java.util.*; public class KahnTopoSort { public static void main(String[] args) { Vertex cs101 = new Vertex("CS101"); Vertex cs102 = new Vertex("CS102"); Vertex cs201 = new Vertex("CS201"); Vertex cs301 = new Vertex("CS30...