Minimize count of unequal elements at corresponding indices between given arrays | C ++ program for the above approach ; Function that count of the mismatched pairs in bot the array ; Create a parent array and initialize it ; Preprocessing of the given pairs of indices ; 1 - based indexing ; If both indices doesn 't belong  to same component ; Insert the indices in same component ; Map to get the indices of array A ; If current element is not present in array B then count this as mismatched ; Get the index of the element in array B ; Check if both indices belong to same connected component if not increment the count ; Return answer ; Function that gives the connected component of each index ; Function that creates the connected components ; Find parent of a and b recursively ; Update the parent of a ; Driver Code ; Given arrays A [ ] , B [ ] ; List of indices ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int find ( int par [ ] , int x ) ; void unionn ( int par [ ] , int a , int b ) ; int countPairs ( int A [ ] , int B [ ] , int N , int M , int List [ ] [ 2 ] ) { int count = 0 ; int par [ N + 1 ] ; for ( int i = 0 ; i <= N ; i ++ ) par [ i ] = i ; for ( int i = 0 ; i < M ; i ++ ) { int index1 = find ( par , List [ i ] [ 0 ] - 1 ) ; int index2 = find ( par , List [ i ] [ 1 ] - 1 ) ; if ( index1 != index2 ) { unionn ( par , index1 , index2 ) ; } } map < int , int > mp ; for ( int i = 0 ; i < N ; i ++ ) { mp [ A [ i ] ] = i ; } for ( int i = 0 ; i < N ; i ++ ) { if ( A [ i ] != B [ i ] ) { if ( mp . find ( B [ i ] ) == mp . end ( ) ) { count ++ ; continue ; } int j = mp [ B [ i ] ] ; if ( find ( par , i ) != find ( par , j ) ) count ++ ; } } return count ; } int find ( int par [ ] , int x ) { if ( par [ x ] == x ) return x ; else return par [ x ] = find ( par , par [ x ] ) ; } void unionn ( int par [ ] , int a , int b ) { a = find ( par , a ) ; b = find ( par , b ) ; if ( a == b ) return ; par [ a ] = b ; } int main ( ) { int N = 5 ; int M = 4 ; int A [ ] = { 1 , 5 , 9 , 2 , 3 } ; int B [ ] = { 2 , 4 , 5 , 1 , 3 } ; int List [ ] [ 2 ] = { { 1 , 4 } , { 2 , 3 } , { 3 , 5 } , { 2 , 5 } } ; cout << countPairs ( A , B , N , M , List ) ; return 0 ; }