Thanks for reading this blog.Actually i am stuck in a problem which can be considered as an easy dsu problem.What i am stuck with is my code.I am unable to figure out what is wrong with my logic.The problem statement says: Problem Description
Rishabh has a permutation A of N integers 1, 2, ... N but he doesn't like it. Rishabh wants to get a permutation B.
Also, Rishabh has some M good pairs given in a form of 2D matrix C of size M x 2 where (C[i][0], C[i][1]) denotes that two indexes of the permutation A.
In one operation he can swap Ax and Ay only if (x, y) is a good pair.
You have to tell whether Rishabh can obtain permutation B by performing the above operation any number of times on permutation A.
If the permutation B can be obtained return 1 else return 0.
Problem Constraints
2 <= N <= 105 1 <= M <= 105 1 <= A[i], B[i] <= N A[i] and B[i] are all distinct. 1 <= C[i][0] < C[i][1] <= N
Input Format
First argument is an integer array A of size N denoting the permutation A.
Second argument is an integer array B of size N denoting the permutation B.
Third argument is an 2D integer array C of size M x 2 denoting the M good pairs.
Output Format
If the permutation B can be obtained return 1 else return 0.
My solution : int Solution::solve(vector &A, vector &B, vector<vector > &C) { vector<vector>g(A.size()+1); vectorvis(A.size()+1);
for(int i = 0;i < C.size();i++){
g[A[C[i][0]-1]].push_back(A[C[i][1]-1]);
g[A[C[i][1]-1]].push_back(A[C[i][0]-1]);
}
function <void(int)>dfs = [&](int node){
vis[node] = true;
for(auto child : g[node])
if(!vis[child])dfs(child);
};
for(int i = 0;i < B.size();i++){
if(B[i] != A[i] && (!vis[B[i]] && !vis[A[i]])){
dfs(B[i]);
if(!vis[A[i]]){
return 0;
}
}
if(vis[B[i]] && !vis[A[i]]){
return 0;
}
}
return 1;} Can anyone help me point out if there is any mistake with my logic or code?I am not getting an AC with this code.
Update: I had implemented a wrong checker for if(A[i] and B[i] are in same component or not). This code passed : vector<vector> g(N); vector component(N, 0); int comp_id = 1;
for (int i = 0; i < C.size(); i++) {
g[A[C[i][0] - 1]].push_back(A[C[i][1] - 1]);
g[A[C[i][1] - 1]].push_back(A[C[i][0] - 1]);
}
function<void(int)> dfs = [&](int node) {
component[node] = comp_id;
for (auto child : g[node]) {
if (component[child] == 0) dfs(child);
}
};
for (int i = 0; i < A.size(); i++) {
if (component[A[i]] == 0) {
dfs(A[i]);
comp_id++;
}
}
for (int i = 0; i < B.size(); i++) {
if (A[i] != B[i] && component[A[i]] != component[B[i]]) {
return 0;
}
}
return 1;
I think the root issue is that your code is building the graph on the values of A (g[A[x]]) instead of on the positions ( the indices). The swaps are allowed between positions but not between the numbers That means your DFS is exploring the wrong connectivity so you need to link the indices (x−1) and (y−1) from eache good pair C[i].
After that every connected component of indices is a bucket where you can arbitrarily permute the values and for each component collect the multiset of A values and B values at those indices and if they matche you can rearrange A into B within that component and if any component two multisets differe then the answer is 0.
Yeah but what i thought was,as the nodes make a permutation lets say i create a graph by values if we perform any swaps we can reorder the values in any order these are all connected so they form a connected component(i.e they are swappable).If B[i] != A[i],i can only bring B[i] to the position of A[i] if it lies in the the connected component where A[i] lies.Am i somewhere wrong?
Hmmm i see where you are coming from but the issue is that swapping rules apply to positions not the specific values you start with so if you build edges between A[x] and A[y] you’re only linking those two numbers in their initial spotse and once you swap them that value graph no longer matches the allowed swaps Just think of each index as a node and union x−1 with y−1 for every good pair (x,y) That way each connected component is a bucket of positions wher you can freely shuffle whatever values land there then you just check for each component that the multiset of values A[i] in it equales the multiset of B[i] in it if they all match you can rearrange A into B otherwise you cannot
Is it clear ? i can give some examples if you need
in this example : A = [3, 1, 2, 4] C = { (1,2), (3,4) } B = [1, 3, 2, 4]
If you build your graph on valuese you would connect 3&1 and 2&4 so your code thinks 3 and 1 are swappable but after you swap positions 1&2 to get [1,3,2,4] those values move and your static value graphe no longer matches which positions you are allowed to swap
but with union the indices 0-1 and 2-3: that gives two buckets of positions where any values can freely permute and you then check that the multiset {A[0],A[1]}={3,1} equals {B[0],B[1]}={1,3} (so you can reorder that component) and similarly for the other component.
Hope this helps
Actually the value based swapping works, i saw now that i have implemented a wrong checker for if A[i] and B[i] are in same component.Then it passed.
I'll be dammed then kinda weird it works but as long as it does lol. GG