2097. Valid Arrangement of Pairs
Approach
Eulerian path — find start node (outDegree - inDegree = 1 or arbitrary); Hierholzer's DFS.
Key Techniques
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
Graph algorithms model relationships between entities. Core algorithms: DFS/BFS for traversal, Dijkstra for weighted shortest path, Bellman-Ford for negative weights, Floyd-Warshall for all-pairs, and Kruskal/Prim for minimum spanning trees. Represent graphs as adjacency lists (Dictionary<int, List<int>>) for efficiency.
An Eulerian circuit visits every edge exactly once. It exists in a directed graph iff every node has equal in-degree and out-degree, and the graph is connected. Hierholzer's algorithm finds it in O(E). Applications: DNA assembly and route planning.
// Approach: Eulerian path — find start node (outDegree - inDegree = 1 or arbitrary); Hierholzer's DFS.
// Time: O(n) Space: O(n)
public class Solution
{
public int[][] ValidArrangement(int[][] pairs)
{
List<int[]> ans = new List<int[]>();
Dictionary<int, Stack<int>> graph = new Dictionary<int, Stack<int>>();
Dictionary<int, int> outDegree = new Dictionary<int, int>();
Dictionary<int, int> inDegrees = new Dictionary<int, int>();
foreach (int[] pair in pairs)
{
int start = pair[0];
int end = pair[1];
if (!graph.ContainsKey(start))
graph[start] = new Stack<int>();
graph[start].Push(end);
outDegree[start] = outDegree.GetValueOrDefault(start, 0) + 1;
inDegrees[end] = inDegrees.GetValueOrDefault(end, 0) + 1;
}
int startNode = GetStartNode(graph, outDegree, inDegrees, pairs);
Euler(graph, startNode, ans);
ans.Reverse();
return ans.ToArray();
}
private int GetStartNode(Dictionary<int, Stack<int>> graph, Dictionary<int, int> outDegree,
Dictionary<int, int> inDegrees, int[][] pairs)
{
foreach (int u in graph.Keys)
{
if (outDegree.GetValueOrDefault(u, 0) - inDegrees.GetValueOrDefault(u, 0) == 1)
return u;
}
return pairs[0][0]; // Arbitrarily choose a node.
}
private void Euler(Dictionary<int, Stack<int>> graph, int u, List<int[]> ans)
{
Stack<int> stack = graph.GetValueOrDefault(u);
while (stack != null && stack.Count > 0)
{
int v = stack.Pop();
Euler(graph, v, ans);
ans.Add(new int[] { u, v });
}
}
}