Chương trình C++ tìm số vị trí cố định tối đa sau hoán vị cho phép

Mô tả bài toán

Cho hoán vị seq độ dài n và m cặp chỉ số cho phép hoán đổi. Thực hiện hoán đổi bất kỳ số lần. Tối đa hóa số vị trí sao cho .

Ví dụ

n=4,m=2, seq={0,3,2,1}, pairs={{0,1},{2,3}}. Đầu ra: 2.

Thuật toán (DSU / Liên thông thành phần)

1. Xây đồ thị các chỉ số có thể hoán đổi (cạnh từ ).
2. Tìm các thành phần liên thông (DFS/BFS/DSU).
3. Trong một thành phần, có thể sắp xếp lại các giá trị tùy ý. Đếm số giá trị trong thành phần mà chỉ số cũng nằm trong thành phần đó → có thể đặt .
4. Cộng thêm các vị trí đã cố định từ đầu ().

Đoạn mã C++

#include <bits/stdc++.h>
using namespace std;

const int N=100;
int tp[N];
vector<int> vtmp[N], vis[N];

void dfs(int u,int comp){
    tp[u]=comp;
    vtmp[comp].push_back(u);
    for(int v:vis[u])
        if(!tp[v]) dfs(v,comp);
}

void solve(int n,int m,int seq[],vector<pair<int,int>> pairs){
    int res=0;
    for(int i=0;i