Minimum Vertex Cover: 최소 정점 덮개

# 이분 그래프 최소 정점 덮개 (König's Theorem)
import sys
from collections import deque
input = sys.stdin.readline
​
def solve():
  n, m, e = map(int, input().split())
  adj = [[] for _ in range(n + 1)]
  for _ in range(e):
      u, v = map(int, input().split())
      adj[u].append(v)
​
  matchL = [-1] * (n + 1)
  matchR = [-1] * (m + 1)
​
  def dfs(u, visited):
      for v in adj[u]:
          if not visited[v]:
              visited[v] = True
              if matchR[v] == -1 or dfs(matchR[v], visited):
                  matchL[u] = v; matchR[v] = u
                  return True
      return False
​
  matching = 0
  for u in range(1, n + 1):
      visited = [False] * (m + 1)
      if dfs(u, visited):
          matching += 1
​
  # König's: 교대 경로 BFS
  visitedL = [False] * (n + 1)
  visitedR = [False] * (m + 1)
  q = deque()
  for u in range(1, n + 1):
      if matchL[u] == -1:
          visitedL[u] = True
          q.append(u)
​
  while q:
      u = q.popleft()
      for v in adj[u]:
          if not visitedR[v]:
              visitedR[v] = True
              w = matchR[v]
              if w != -1 and not visitedL[w]:
                  visitedL[w] = True
                  q.append(w)
​
  # MVC = (Left \ visitedL) ∪ visitedR
  mvc = []
  for u in range(1, n + 1):
      if not visitedL[u]: mvc.append(f"L{u}")
  for v in range(1, m + 1):
      if visitedR[v]: mvc.append(f"R{v}")
​
  print(f"Matching size: {matching}")
  print(f"MVC size: {len(mvc)}")
  print(*mvc)
​
solve()

// 이분 그래프 최소 정점 덮개 (König's Theorem)
import java.util.*;
import java.io.*;
​
public class Main {
  static int n, m;
  static List<Integer>[] adj;
  static int[] matchL, matchR;
  static boolean[] visited;
​
  static boolean dfs(int u) {
      for (int v : adj[u]) {
          if (!visited[v]) {
              visited[v] = true;
              if (matchR[v] == -1 || dfs(matchR[v])) {
                  matchL[u] = v; matchR[v] = u; return true;
              }
          }
      }
      return false;
  }
​
  @SuppressWarnings("unchecked")
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      n = Integer.parseInt(st.nextToken());
      m = Integer.parseInt(st.nextToken());
      int e = Integer.parseInt(st.nextToken());
​
      adj = new List[n + 1];
      for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
      matchL = new int[n + 1]; matchR = new int[m + 1];
      Arrays.fill(matchL, -1); Arrays.fill(matchR, -1);
​
      for (int i = 0; i < e; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          adj[u].add(v);
      }
​
      int matching = 0;
      visited = new boolean[m + 1];
      for (int u = 1; u <= n; u++) {
          Arrays.fill(visited, false);
          if (dfs(u)) matching++;
      }
​
      // König's: 교대 경로 BFS
      boolean[] visitedL = new boolean[n + 1];
      boolean[] visitedR = new boolean[m + 1];
      Queue<Integer> q = new LinkedList<>();
      for (int u = 1; u <= n; u++) {
          if (matchL[u] == -1) { visitedL[u] = true; q.add(u); }
      }
      while (!q.isEmpty()) {
          int u = q.poll();
          for (int v : adj[u]) {
              if (!visitedR[v]) {
                  visitedR[v] = true;
                  int w = matchR[v];
                  if (w != -1 && !visitedL[w]) { visitedL[w] = true; q.add(w); }
              }
          }
      }
​
      StringBuilder sb = new StringBuilder();
      sb.append("Matching size: ").append(matching).append('\n');
      List<String> mvc = new ArrayList<>();
      for (int u = 1; u <= n; u++) if (!visitedL[u]) mvc.add("L" + u);
      for (int v = 1; v <= m; v++) if (visitedR[v]) mvc.add("R" + v);
      sb.append("MVC size: ").append(mvc.size()).append('\n');
      for (String s : mvc) sb.append(s).append(' ');
      System.out.println(sb);
  }
}