并查集（Union-Find），又称不相交集合数据结构，是一种用于处理集合合并和查询问题的数据结构。它通常用于解决元素之间的分组问题，如连通分量问题、集合划分等。



并查集主要支持两种操作：

1. `Union`（合并）：将两个不相交的集合合并成一个集合。
2. `Find`（查询）：确定元素属于哪个集合，或者找到某个集合的代表元素。

通常情况下，并查集包括以下几个基本操作和概念：

- **初始化**：初始化并查集，通常将每个元素视为一个独立的集合，即每个元素是其自身的代表。

- **`Find` 操作**：用于查找元素所属的集合，通常通过沿着父节点链向上查找，直到找到代表元素（根节点）。这个操作通常包括路径压缩，即将路径上的每个节点都直接连接到根节点，以优化查询操作的性能。

- **`Union` 操作**：用于合并两个不相交的集合，通常通过将其中一个集合的根节点指向另一个集合的根节点，或者将其中一个根节点连接到另一个根节点。

在实际应用中，你可以使用一个数组或向量来表示并查集的元素，其中数组的索引表示元素，数组的值表示该元素的父节点。初始状态下，每个元素的父节点是自身。

**应用场景**：
并查集主要用于解决元素的分组问题，例如：

1. **连通分量问题**：在图论中，用于查找图中的连通分量，即图中的不相交子图。
2. **集合划分问题**：将一个元素集合分为若干个不相交的子集。
3. **Kruskal 算法**：用于构建最小生成树。
4. **网络连接问题**：查找网络中的连接关系。
5. **解决运算的等价关系**：如解决数学等价关系问题。
6. **分组问题**：将元素分为不相交的组。

**基本思想**：
并查集的基本思想是用树结构表示集合，每个树的根节点表示集合的代表元素。合并操作即将两个树合并成一个，查询操作即查找元素所在的集合根节点。路径压缩是一种优化方法，通过将查找路径上的每个节点直接连接到根节点，可以显著提高查询操作的效率。

并查集是一种高效且容易实现的数据结构，适用于解决多种实际问题中的分组和连接关系问题。
P3367


```cpp
#include <iostream>
#include <vector>

using namespace std;

vector<int> parent; // Parent array for Union-Find

// Initialize the Union-Find data structure with n elements
void initialize(int n) {
    parent.resize(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i; // Each element is initially its own parent
    }
}

// Find the root (representative) of the set to which element x belongs
int find(int x) {
    if (x == parent[x]) {
        return x; // x is the root of its set
    }
    return parent[x] = find(parent[x]); // Path compression for optimization
}

// Union (merge) the sets to which elements x and y belong
void unite(int x, int y) {
    x = find(x); // Find the root of x's set
    y = find(y); // Find the root of y's set

    if (x != y) {
        parent[x] = y; // Make one of them the parent of the other
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    initialize(n); // Initialize Union-Find with n elements

    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            unite(x - 1, y - 1); // Adjust for 0-based indexing
        } else if (op == 2) {
            int root_x = find(x - 1);
            int root_y = find(y - 1);
            if (root_x == root_y) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        }
    }

    return 0;
}

```

并查集 

字符串哈希（String Hashing）是一种将字符串映射成整数值的技术。它在解决字符串相关问题中非常有用，例如在计算不同字符串的数量、字符串匹配、模式匹配等问题中广泛应用。下面详细讲解字符串哈希的原理和用途：
**原理：**



1. 选择一个适当的基数（通常选择一个质数），如常用的 31 或 53。这个基数将作为哈希函数的参数，通常称为“质数模”。
2. 对字符串中的每个字符，将其转化为一个整数值（例如，字符 'a' 可以映射为 0，'b' 可以映射为 1，依此类推）。
3. 使用选择的基数作为模数，依次对字符串中的字符进行哈希操作，计算出一个哈希值。
   哈希值的计算方式通常为：`hash_value = (hash_value * base + char_value) % modulo`
   - `hash_value` 是当前字符串的哈希值，初始化为 0。
   - `base` 是所选的基数。
   - `char_value` 是当前字符的整数值（例如，字符 'a' 对应的整数值）。
   - `modulo` 是一个用来防止哈希值溢出的模数，通常选取一个较大的质数。
4. 重复步骤 3，直到对字符串中的所有字符都进行了哈希操作，最终得到的 `hash_value` 即为字符串的哈希值。
**用途：**
字符串哈希的主要用途包括：
1. 计算字符串的哈希值后，可以将字符串与其哈希值相关联，以便快速比较字符串是否相等。如果两个字符串的哈希值相同，那么它们可能相等。
2. 计算不同字符串的数量：通过将每个字符串的哈希值存储在一个哈希表中，可以快速查找并统计不同字符串的数量。
3. 字符串匹配和模式匹配：哈希值可用于快速比较较长字符串的部分内容，以判断是否匹配。这在一些搜索和匹配算法中非常有用。
4. 数据压缩和数据索引：字符串哈希值可以用于压缩和索引数据，提高数据的检索速度。
需要注意的是，字符串哈希虽然在很多问题中有用，但它也存在一些局限性。例如，不同字符串可能有相同的哈希值，这就是哈希碰撞。为了减小哈希碰撞的概率，通常会选择一个较大的质数作为模数，并谨慎选择哈希函数的基数。


```go
#include <iostream>
#include <vector>

// 自定义哈希函数，用于计算字符串的哈希值
int customHash(const std::string& str) {
    int prime = 31; // 选择一个较大的质数
    int hashValue = 0;

    for (char c : str) {
        hashValue = (hashValue * prime + c) % 1000000007; // 防止哈希值溢出
    }

    return hashValue;
}

int main() {
    int N;
    std::cin >> N; // 读取字符串的个数

    std::vector<std::string> strings; // 用于存储输入的字符串
    std::vector<int> hashValues; // 用于存储字符串的哈希值
    int uniqueCount = 0; // 用于记录不同字符串的数量

    for (int i = 0; i < N; ++i) {
        std::string str;
        std::cin >> str; // 读取每个字符串

        int hashValue = customHash(str); // 计算字符串的哈希值
        bool isUnique = true;

        for (int j = 0; j < i; ++j) {
            // 检查是否已存在相同哈希值的字符串
            if (hashValues[j] == hashValue) {
                isUnique = false;
                break;
            }
        }

        if (isUnique) {
            strings.push_back(str); // 如果是新字符串，存储它
            hashValues.push_back(hashValue); // 存储哈希值
            uniqueCount++; // 唯一字符串数量加一
        }
    }

    std::cout << uniqueCount << std::endl; // 输出不同字符串的数量

    return 0;
}

```

字符串哈希 P3370

P3390




```cpp
#include <iostream>
#include <vector>
#include <cstring>

const int MOD = 1000000007;

// 定义一个矩阵结构
struct Matrix {
    int n;  // 矩阵的维度
    std::vector<std::vector<int>> data;  // 矩阵数据

    Matrix(int _n) : n(_n), data(_n, std::vector<int>(_n, 0)) {}

    // 创建并返回一个单位矩阵
    static Matrix identity(int n) {
        Matrix mat(n);
        for (int i = 0; i < n; ++i) {
            mat.data[i][i] = 1;
        }
        return mat;
    }

    // 矩阵相乘操作
    Matrix operator*(const Matrix& other) const {
        Matrix result(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    // 用模运算防止整数溢出
                    result.data[i][j] = (result.data[i][j] + 1LL * data[i][k] * other.data[k][j] % MOD) % MOD;
                }
            }
        }
        return result;
    }
};

// 矩阵的高次幂计算
Matrix matrixPower(Matrix mat, long long k) {
    int n = mat.n;
    Matrix result = Matrix::identity(n);
    while (k) {
        if (k % 2) {
            result = result * mat;
        }
        mat = mat * mat;
        k /= 2;
    }
    return result;
}

int main() {
    int n, k;
    std::cin >> n >> k;
    Matrix A(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> A.data[i][j];
        }
    }

    Matrix result = matrixPower(A, k);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << result.data[i][j] << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

```

矩阵快速幂模板题

主要是一些选举细节代码，不包含其他逻辑，主要是选举部分逻辑



# 初始化时等待就绪
```go
func NewConsensusModule(id int, peerIds []int, server *Server, ready <-chan interface{}) *ConsensusModule {
	cm := new(ConsensusModule)
	cm.id = id
	cm.peerIds = peerIds
	cm.server = server
	cm.state = Follower
	cm.votedFor = -1

	go func() {  // 等待就绪
		// The CM is quiescent until ready is signaled; then, it starts a countdown
		// for leader election.
		<-ready
		cm.mu.Lock()
		cm.electionResetEvent = time.Now()  //重置选举时间
		cm.mu.Unlock()
		cm.runElectionTimer()
	}()

	return cm
}
```
# 开始决定是否投票

```go
// RequestVote RPC.
func (cm *ConsensusModule) RequestVote(args RequestVoteArgs, reply *RequestVoteReply) error {
	cm.mu.Lock()
	defer cm.mu.Unlock()
	if cm.state == Dead {
		return nil
	}
	cm.dlog("RequestVote: %+v [currentTerm=%d, votedFor=%d]", args, cm.currentTerm, cm.votedFor)

	if args.Term > cm.currentTerm {
		cm.dlog("... term out of date in RequestVote")
		cm.becomeFollower(args.Term)
	}

	if cm.currentTerm == args.Term &&
		(cm.votedFor == -1 || cm.votedFor == args.CandidateId) {
		reply.VoteGranted = true
		cm.votedFor = args.CandidateId
		cm.electionResetEvent = time.Now()
	} else {
		reply.VoteGranted = false
	}
	reply.Term = cm.currentTerm
	cm.dlog("... RequestVote reply: %+v", reply)
	return nil
}
```
# 同步日志

```go
func (cm *ConsensusModule) AppendEntries(args AppendEntriesArgs, reply *AppendEntriesReply) error {
	cm.mu.Lock()
	defer cm.mu.Unlock()
	if cm.state == Dead {
		return nil
	}
	cm.dlog("AppendEntries: %+v", args)

	if args.Term > cm.currentTerm {
		cm.dlog("... term out of date in AppendEntries")
		cm.becomeFollower(args.Term)
	}

	reply.Success = false
	if args.Term == cm.currentTerm {
		if cm.state != Follower {
			cm.becomeFollower(args.Term)
		}
		cm.electionResetEvent = time.Now()  //相当于是心跳一次
		reply.Success = true
	}

	reply.Term = cm.currentTerm
	cm.dlog("AppendEntries reply: %+v", *reply)
	return nil
}
```
# 生成选举超时时间

```go
// electionTimeout generates a pseudo-random election timeout duration.
func (cm *ConsensusModule) electionTimeout() time.Duration {
	// If RAFT_FORCE_MORE_REELECTION is set, stress-test by deliberately
	// generating a hard-coded number very often. This will create collisions
	// between different servers and force more re-elections.
	if len(os.Getenv("RAFT_FORCE_MORE_REELECTION")) > 0 && rand.Intn(3) == 0 {
		return time.Duration(150) * time.Millisecond
	} else {
		return time.Duration(150+rand.Intn(150)) * time.Millisecond
	}
}
```
# 选举触发
不断的判断领导是否存活
```go
// runElectionTimer 实现了一个选举计时器。当我们希望启动一个计时器以开始新一轮选举时，
// 应该调用这个方法。这个方法是阻塞的，应该在一个单独的 goroutine 中运行。
// 它为单次（one-shot）的选举计时器设计，因为它会在以下情况下退出：
// - 当 CM 的状态从 Follower/Candidate 改变时
// - 当当前任期（term）改变时
func (cm *ConsensusModule) runElectionTimer() {
	timeoutDuration := cm.electionTimeout() // 获取选举超时时间间隔
	cm.mu.Lock()
	termStarted := cm.currentTerm // 记录选举计时器启动时的当前任期
	cm.mu.Unlock()
	cm.dlog("election timer started (%v), term=%d", timeoutDuration, termStarted)

// 以下是一个循环，它会一直运行，直到发生以下情况之一：
// - 我们发现选举计时器不再需要，或
// - 选举计时器超时，该 CM 成为 Candidate
// 在 Follower 中，这通常在 CM 的生命周期中一直在后台运行。

	ticker := time.NewTicker(10 * time.Millisecond)
	defer ticker.Stop()
	for {
		<-ticker.C

		cm.mu.Lock()
		// 如果 CM 的状态变成 Candidate 或 Follower，则退出选举计时器
		if cm.state != Candidate && cm.state != Follower {
			cm.dlog("在选举计时器中，状态=%s，退出", cm.state)
			cm.mu.Unlock()
			return
		}

		// 如果当前任期（term）改变，则退出选举计时器
		if termStarted != cm.currentTerm {
			cm.dlog("在选举计时器中，任期从 %d 变为 %d，退出", termStarted, cm.currentTerm)
			cm.mu.Unlock()
			return
		}

		// 如果经过了选举超时时间间隔，而且我们还没有收到领袖的消息或者没有投票给其他 Candidate，
		// 则开始一轮新的选举。
		if elapsed := time.Since(cm.electionResetEvent); elapsed >= timeoutDuration {
			cm.startElection()
			cm.mu.Unlock()
			return
		}
		cm.mu.Unlock()
	}
}

```

# 开始选举

```go
// startElection starts a new election with this CM as a candidate.
// Expects cm.mu to be locked.
func (cm *ConsensusModule) startElection() {
	cm.state = Candidate
	cm.currentTerm += 1
	savedCurrentTerm := cm.currentTerm
	cm.electionResetEvent = time.Now()
	cm.votedFor = cm.id
	cm.dlog("becomes Candidate (currentTerm=%d); log=%v", savedCurrentTerm, cm.log)

	votesReceived := 1

	// Send RequestVote RPCs to all other servers concurrently.
	for _, peerId := range cm.peerIds {
		go func(peerId int) {
			args := RequestVoteArgs{
				Term:        savedCurrentTerm,
				CandidateId: cm.id,
			}
			var reply RequestVoteReply

			cm.dlog("sending RequestVote to %d: %+v", peerId, args)
			if err := cm.server.Call(peerId, "ConsensusModule.RequestVote", args, &reply); err == nil {
				cm.mu.Lock()
				defer cm.mu.Unlock()
				cm.dlog("received RequestVoteReply %+v", reply)

				if cm.state != Candidate {
					cm.dlog("while waiting for reply, state = %v", cm.state)
					return
				}

				if reply.Term > savedCurrentTerm {
					cm.dlog("term out of date in RequestVoteReply")
					cm.becomeFollower(reply.Term)
					return
				} else if reply.Term == savedCurrentTerm {
					if reply.VoteGranted {
						votesReceived += 1
						if votesReceived*2 > len(cm.peerIds)+1 {
							// Won the election!
							cm.dlog("wins election with %d votes", votesReceived)
							cm.startLeader()
							return
						}
					}
				}
			}
		}(peerId)
	}

	// Run another election timer, in case this election is not successful.
	go cm.runElectionTimer()
}

```
# 成为Fllower

```go
// becomeFollower makes cm a follower and resets its state.
// Expects cm.mu to be locked.
func (cm *ConsensusModule) becomeFollower(term int) {
	cm.dlog("becomes Follower with term=%d; log=%v", term, cm.log)
	cm.state = Follower
	cm.currentTerm = term
	cm.votedFor = -1
	cm.electionResetEvent = time.Now()

	go cm.runElectionTimer()
}
```
# Leader

```go
// startLeader switches cm into a leader state and begins process of heartbeats.
// Expects cm.mu to be locked.
func (cm *ConsensusModule) startLeader() {
	cm.state = Leader
	cm.dlog("becomes Leader; term=%d, log=%v", cm.currentTerm, cm.log)

	go func() {
		ticker := time.NewTicker(50 * time.Millisecond)
		defer ticker.Stop()

		// Send periodic heartbeats, as long as still leader.
		for {
			cm.leaderSendHeartbeats()
			<-ticker.C

			cm.mu.Lock()
			if cm.state != Leader {
				cm.mu.Unlock()
				return
			}
			cm.mu.Unlock()
		}
	}()
}
```

# 发送心跳

```go
// leaderSendHeartbeats sends a round of heartbeats to all peers, collects their
// replies and adjusts cm's state.
func (cm *ConsensusModule) leaderSendHeartbeats() {
	cm.mu.Lock()
	if cm.state != Leader {
		cm.mu.Unlock()
		return
	}
	savedCurrentTerm := cm.currentTerm
	cm.mu.Unlock()

	for _, peerId := range cm.peerIds {
		args := AppendEntriesArgs{
			Term:     savedCurrentTerm,
			LeaderId: cm.id,
		}
		go func(peerId int) {
			cm.dlog("sending AppendEntries to %v: ni=%d, args=%+v", peerId, 0, args)
			var reply AppendEntriesReply
			if err := cm.server.Call(peerId, "ConsensusModule.AppendEntries", args, &reply); err == nil {
				cm.mu.Lock()
				defer cm.mu.Unlock()
				if reply.Term > savedCurrentTerm {
					cm.dlog("term out of date in heartbeat reply")
					cm.becomeFollower(reply.Term)
					return
				}
			}
		}(peerId)
	}
}
```

raft一些选举细节

```go
// CommitEntry 是 Raft 用来向 commit 通道报告的数据。每个 commit 条目通知客户端一致性已经在一个命令上达成，并且它可以应用于客户端的状态机。
type CommitEntry struct {
	// Command 是正在提交的客户端命令。
	Command interface{}

	// Index 是客户端命令被提交的日志索引。
	Index int

	// Term 是客户端命令被提交的 Raft 任期。
	Term int
}

// CMState 表示 Raft 一致性模块的状态。
type CMState int

const (
	Follower CMState = iota    // 跟随者状态
	Candidate                  // 候选人状态
	Leader                     // 领导者状态
	Dead                       // 无效状态
)

func (s CMState) String() string {
	switch s {
	case Follower:
		return "跟随者"
	case Candidate:
		return "候选人"
	case Leader:
		return "领导者"
	case Dead:
		return "无效状态"
	default:
		panic("不可达的状态")
	}
}

// LogEntry 表示 Raft 日志条目。
type LogEntry struct {
	Command interface{} // 日志条目中的命令
	Term    int         // 日志条目所属的 Raft 任期
}

// ConsensusModule (CM) 实现 Raft 一致性的单个节点。
type ConsensusModule struct {
	// mu 保护对 CM 的并发访问。
	mu sync.Mutex

	// id 是此 CM 的服务器 ID。
	id int

	// peerIds 列出了集群中同伴的 ID。
	peerIds []int

	// server 是包含此 CM 的服务器。它用于向同伴发出 RPC 调用。
	server *Server

	// storage 用于持久化状态。
	storage Storage

	// commitChan 是此 CM 将报告提交的日志条目的通道。在构建过程中由客户端传递。
	commitChan chan<- CommitEntry

	// newCommitReadyChan 是内部通知通道，用于通知提交新条目的 goroutines 可能会发送到 commitChan。
	newCommitReadyChan chan struct{}

	// triggerAEChan 是内部通知通道，用于在发生重要更改时触发向跟随者发送新 AEs。
	triggerAEChan chan struct{}

	// 持久化在所有服务器上的 Raft 状态
	currentTerm int
	votedFor    int
	log         []LogEntry

	// 所有服务器上的易失性 Raft 状态
	commitIndex        int
	lastApplied        int
	state              CMState
	electionResetEvent time.Time

	// 领导者的 Raft 状态
	nextIndex  map[int]int
	matchIndex map[int]int
}

// RequestVoteArgs 表示 RequestVote RPC 的参数。
type RequestVoteArgs struct {
	Term         int // 请求方的当前任期
	CandidateId  int // 请求方的候选人 ID
	LastLogIndex int // 请求方的最后日志索引
	LastLogTerm  int // 请求方的最后日志的任期
}

// RequestVoteReply 表示 RequestVote RPC 的回复。
type RequestVoteReply struct {
	Term        int  // 接收方的当前任期
	VoteGranted bool // 是否授予投票
}

// AppendEntriesArgs 表示 AppendEntries RPC 的参数。
type AppendEntriesArgs struct {
	Term     int         // 领导者的当前任期
	LeaderId int         // 领导者的 ID
	PrevLogIndex int     // 先前日志条目的索引
	PrevLogTerm  int     // 先前日志条目的任期
	Entries      []LogEntry // 要附加到日志的条目
	LeaderCommit int     // 领导者的提交索引
}

// AppendEntriesReply 表示 AppendEntries RPC 的回复。
type AppendEntriesReply struct {
	Term    int  // 接收方的当前任期
	Success bool // 是否成功
	// 更快的冲突解决优化（在文档第 5.3 节末尾有描述）
	ConflictIndex int // 冲突索引
	ConflictTerm  int // 冲突任期
}

```