hopcroft_karp.go

package main

import (
    "fmt"
)

type HopcroftKarp struct {
    graph     map[string][]string
    matching  map[string]string
    visited   map[string]bool
}

func NewHopcroftKarp(graph map[string][]string) *HopcroftKarp {
    return &HopcroftKarp{
        graph:    graph,
        matching: make(map[string]string),
        visited:  make(map[string]bool),
    }
}

func (hk *HopcroftKarp) BipartiteMatching() map[string]string {
    for u := range hk.graph {
        if _, exists := hk.matching[u]; !exists {
            hk.visited = make(map[string]bool)
            hk.dfs(u)
            hk.visited = make(map[string]bool)
        }
    }
    return hk.matching
}

func (hk *HopcroftKarp) dfs(u string) bool {
    if hk.visited[u] {
        return false
    }
    hk.visited[u] = true

    for _, v := range hk.graph[u] {
        if _, exists := hk.matching[v]; !exists || hk.dfs(hk.matching[v]) {
            hk.matching[u] = v
            hk.matching[v] = u
            return true
        }
    }
    return false
}

func main() {
    graph := map[string][]string{
        "A": []string{"X", "Y"},
        "B": []string{"X"},
        "C": []string{"Y"},
        "D": []string{},
    }

    hk := NewHopcroftKarp(graph)
    matching := hk.BipartiteMatching()
    fmt.Println(matching)
}