โปรแกรม C++ หาค่า i สูงสุดที่ทำให้ seq[i] = i หลังสลับได้

มี permutation seq ขนาด n และ m คู่ดัชนี pairs (ค่า 0..n-1) สามารถทำซ้ำได้ไม่จำกัด: เลือก j สลับ seq[pairs[j].first] กับ seq[pairs[j].second] หา i สูงสุดที่ทำให้ seq[i] = i ได้หลังสลับอย่างเหมาะสม

ตัวอย่าง: n=4,m=2, seq={0,3,2,1}, pairs={{0,1},{2,3}} ผลลัพธ์: 2

ขั้นตอนการแก้ปัญหา (Connected Components + DFS)

สร้างกราฟ vis จาก pairs (ขอบไม่มีทิศทาง)
หา Connected Components ด้วย DFS ใส่ป้าย tp[v] = component_id เก็บสมาชิกใน vtmp[comp]

res

i

seq[i]==i

สำหรับแต่ละ Component: ถ้ามี j ใน component ที่ tp[seq[j]] == comp และ seq[j] != j → สลับได้ให้ seq[j]=j เพิ่ม res++
คืน res

ตัวอย่างโค้ด C++

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

#define N 100
int tp[N];
vector<int> vtmp[N], vis[N];

void dfs(int j, int k) {
    tp[j] = k;
    vtmp[k].push_back(j);
    for (auto b : vis[j])
        if (tp[b] == 0) dfs(b, k);
}

void solve(int n, int m, int seq[], vector<pair<int,int>> pairs) {
    int res = 0;
    for (int i = 0; i < n; i++) if (seq[i] == i) res++;
    for (int i = 0; i < m; i++) {
        int a = pairs[i].first, b = pairs[i].second;
        vis[a].push_back(b); vis[b].push_back(a);
    }
    int idx = 1;
    for (int i = 0; i < n; i++) if (tp[i] == 0) {
        dfs(i, idx);
        for (auto j : vtmp[idx])
            if (tp[seq[j]] == idx && seq[j] != j) res++;
        idx++;
    }
    cout << res;
}

int main() {
    int n = 4, m = 2, seq[] = {0, 3, 2, 1};
    vector<pair<int,int>> pairs = {{0,1},{2,3}};
    solve(n, m, seq, pairs);
    return 0;
}

อินพุต / เอาต์พุต

Input: 4, 2, {0,3,2,1}, {{0,1},{2,3}}

Output: 2