Graphs

from collections import defaultdict, deque

class Graph:
    def __init__(self, directed=False):
        # defaultdict(list) creates an empty list for any new key automatically
        # This avoids KeyError when accessing a vertex with no edges yet
        self.adj = defaultdict(list)
        self.directed = directed

    def add_edge(self, u, v, weight=1):
        """Add an edge from vertex u to vertex v with optional weight."""
        self.adj[u].append((v, weight))
        if not self.directed:
            # Undirected: add the reverse edge too
            self.adj[v].append((u, weight))

    def add_vertex(self, v):
        """Ensure vertex v exists even if it has no edges."""
        if v not in self.adj:
            self.adj[v] = []

    def bfs(self, start):
        """Traverse the graph in BFS order from start.
        Returns list of vertices in the order they were discovered.
        BFS visits vertices layer by layer — all vertices at distance d
        before any vertex at distance d+1."""
        visited = {start}         # Set of vertices we've already seen
        queue = deque([start])    # deque is O(1) for both append and popleft
        order = []                # The final traversal order

        while queue:
            node = queue.popleft()   # Take the OLDEST vertex (FIFO)
            order.append(node)

            for neighbor, _ in self.adj[node]:
                if neighbor not in visited:
                    visited.add(neighbor)    # Mark BEFORE enqueuing
                    queue.append(neighbor)   # to prevent duplicates in queue
        return order

    def dfs(self, start):
        """Traverse the graph in DFS order from start (iterative).
        Returns list of vertices in the order they were discovered.
        DFS plunges deep before exploring breadth."""
        visited = set()
        stack = [start]
        order = []

        while stack:
            node = stack.pop()      # Take the NEWEST vertex (LIFO)
            if node in visited:
                continue            # Skip if already processed
            visited.add(node)
            order.append(node)

            # Push neighbors in reverse to visit in natural order
            # (stack reverses the order, so we reverse first)
            for neighbor, _ in reversed(self.adj[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
        return order

    def has_cycle_directed(self):
        """Detect cycles in a DIRECTED graph using DFS 3-color method.
        WHITE (0) = unvisited, GRAY (1) = in current DFS path,
        BLACK (2) = fully processed. A back edge (hitting GRAY) means cycle."""
        WHITE, GRAY, BLACK = 0, 1, 2
        color = defaultdict(int)  # default WHITE

        def _dfs(node):
            color[node] = GRAY    # Entering this node's DFS subtree
            for neighbor, _ in self.adj[node]:
                if color[neighbor] == GRAY:
                    return True   # Back edge! Cycle found.
                if color[neighbor] == WHITE and _dfs(neighbor):
                    return True
            color[node] = BLACK   # Done with this node entirely
            return False

        # Must check all vertices (graph may be disconnected)
        return any(
            _dfs(v) for v in self.adj if color[v] == WHITE
        )

    def has_cycle_undirected(self):
        """Detect cycles in an UNDIRECTED graph using DFS with parent tracking.
        If we reach an already-visited neighbor that isn't our parent,
        that's a cycle."""
        visited = set()

        def _dfs(node, parent):
            visited.add(node)
            for neighbor, _ in self.adj[node]:
                if neighbor not in visited:
                    if _dfs(neighbor, node):
                        return True
                elif neighbor != parent:
                    return True  # Visited neighbor that isn't parent = cycle
            return False

        for v in self.adj:
            if v not in visited:
                if _dfs(v, -1):
                    return True
        return False

    def shortest_path_bfs(self, start, end):
        """Find shortest path in an UNWEIGHTED graph using BFS.
        Returns the path as a list of vertices, or empty list if no path."""
        if start == end:
            return [start]

        visited = {start}
        queue = deque([(start, [start])])  # (vertex, path_so_far)

        while queue:
            node, path = queue.popleft()
            for neighbor, _ in self.adj[node]:
                if neighbor not in visited:
                    new_path = path + [neighbor]
                    if neighbor == end:
                        return new_path
                    visited.add(neighbor)
                    queue.append((neighbor, new_path))
        return []  # No path exists


# Usage examples
g = Graph(directed=False)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)

print("BFS from 0:", g.bfs(0))          # [0, 1, 2, 3, 4]
print("DFS from 0:", g.dfs(0))          # [0, 1, 3, 2, 4] or similar
print("Shortest 0→4:", g.shortest_path_bfs(0, 4))  # [0, 1, 3, 4]
print("Has cycle:", g.has_cycle_undirected())       # True (0-1-3-2-0)

from collections import deque, defaultdict

def topological_sort(num_vertices, edges):
    """Kahn's algorithm for topological sorting.
    
    Topological sort: order vertices so that for every directed edge u→v,
    u comes before v. Only possible on DAGs (no cycles).
    
    Args:
        num_vertices: number of vertices (labeled 0 to n-1)
        edges: list of (u, v) pairs meaning u must come before v
    
    Returns:
        List of vertices in topological order, or empty list if cycle exists.
    """
    # Build adjacency list and count incoming edges for each vertex
    adj = defaultdict(list)
    in_degree = [0] * num_vertices  # How many edges point INTO each vertex

    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1

    # Start with vertices that have no prerequisites (in-degree 0)
    queue = deque()
    for v in range(num_vertices):
        if in_degree[v] == 0:
            queue.append(v)

    order = []
    while queue:
        node = queue.popleft()
        order.append(node)

        # "Remove" this node by decrementing in-degree of its neighbors
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)  # All prerequisites satisfied

    # If we processed all vertices, the sort succeeded
    # If not, a cycle prevented some vertices from reaching in-degree 0
    if len(order) != num_vertices:
        return []   # Cycle detected!
    return order


# Example: course prerequisites
# Course 1 requires Course 0, Course 2 requires Course 1, etc.
edges = [(0, 1), (1, 2), (0, 3), (3, 2)]
print(topological_sort(4, edges))  # [0, 1, 3, 2] or [0, 3, 1, 2]

class Graph {
  constructor(directed = false) {
    this.adj = new Map();  // vertex → array of {node, weight}
    this.directed = directed;
  }

  addVertex(v) {
    if (!this.adj.has(v)) this.adj.set(v, []);
  }

  addEdge(u, v, weight = 1) {
    this.addVertex(u);
    this.addVertex(v);
    this.adj.get(u).push({ node: v, weight });
    if (!this.directed) {
      this.adj.get(v).push({ node: u, weight });
    }
  }

  bfs(start) {
    const visited = new Set([start]);
    const queue = [start];     // Use array as queue (shift is O(n) but fine for interviews)
    const order = [];
    let front = 0;             // Pointer optimization: avoid shift()

    while (front < queue.length) {
      const node = queue[front++];  // Dequeue from front
      order.push(node);

      for (const { node: neighbor } of this.adj.get(node) || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    return order;
  }

  dfs(start) {
    const visited = new Set();
    const stack = [start];
    const order = [];

    while (stack.length) {
      const node = stack.pop();
      if (visited.has(node)) continue;
      visited.add(node);
      order.push(node);

      // Push in reverse for natural ordering
      const neighbors = this.adj.get(node) || [];
      for (let i = neighbors.length - 1; i >= 0; i--) {
        if (!visited.has(neighbors[i].node)) {
          stack.push(neighbors[i].node);
        }
      }
    }
    return order;
  }

  // Count connected components in an undirected graph
  connectedComponents() {
    const visited = new Set();
    let count = 0;

    for (const vertex of this.adj.keys()) {
      if (!visited.has(vertex)) {
        count++;
        // BFS/DFS to mark all vertices in this component
        const stack = [vertex];
        while (stack.length) {
          const node = stack.pop();
          if (visited.has(node)) continue;
          visited.add(node);
          for (const { node: neighbor } of this.adj.get(node) || []) {
            if (!visited.has(neighbor)) stack.push(neighbor);
          }
        }
      }
    }
    return count;
  }
}

from collections import defaultdict, Counter

class SocialNetwork:
    """Simplified friend suggestion engine using graph traversal."""

    def __init__(self):
        self.friends = defaultdict(set)  # user → set of friends

    def add_friendship(self, user_a, user_b):
        """Friendships are bidirectional (undirected edge)."""
        self.friends[user_a].add(user_b)
        self.friends[user_b].add(user_a)

    def suggest_friends(self, user, max_suggestions=5):
        """Suggest people the user might know, ranked by mutual friends.

        Algorithm:
        1. Get all friends-of-friends (distance 2 in the graph)
        2. Exclude people who are already friends
        3. Rank by number of mutual connections (higher = stronger signal)
        """
        direct_friends = self.friends[user]
        mutual_count = Counter()  # candidate → how many mutual friends

        for friend in direct_friends:
            for fof in self.friends[friend]:  # friends-of-friends
                if fof != user and fof not in direct_friends:
                    mutual_count[fof] += 1

        # Sort by mutual friend count (descending), then by name for ties
        ranked = sorted(mutual_count.items(),
                       key=lambda x: (-x[1], x[0]))

        return [(person, count) for person, count in ranked[:max_suggestions]]

    def degrees_of_separation(self, user_a, user_b):
        """BFS to find shortest path length between two users.
        Returns -1 if they're not connected at all."""
        if user_a == user_b:
            return 0

        visited = {user_a}
        queue = [(user_a, 0)]
        front = 0

        while front < len(queue):
            node, dist = queue[front]
            front += 1

            for neighbor in self.friends[node]:
                if neighbor == user_b:
                    return dist + 1
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, dist + 1))

        return -1  # Not connected


# Demo
network = SocialNetwork()
network.add_friendship("Alice", "Bob")
network.add_friendship("Alice", "Charlie")
network.add_friendship("Bob", "Charlie")
network.add_friendship("Bob", "David")
network.add_friendship("Charlie", "David")
network.add_friendship("Charlie", "Eve")
network.add_friendship("David", "Frank")

suggestions = network.suggest_friends("Alice")
print("Friend suggestions for Alice:")
for person, mutual in suggestions:
    print(f"  {person} ({mutual} mutual friends)")
# Output:
#   David (2 mutual friends)  — connected through Bob AND Charlie
#   Eve (1 mutual friends)    — connected through Charlie
#   Frank (0 mutual friends)  — wait, actually 0? No, through David...

print(f"\nDegrees of separation (Alice→Frank): "
      f"{network.degrees_of_separation('Alice', 'Frank')}")  # 3