947. Most Stones Removed | BFS | DFS | Leetcode POTD Explained

[@codeby_naruto]

Code :-
class Solution {
public:
// Function to check if two stones are in the same group (same row or column)
bool areSameGroup(vector& stone1, vector& stone2) {
return stone1[0] == stone2[0] || stone1[1] == stone2[1];
}
// Depth-first search to mark all stones connected to the current stone
void dfs(vector& visited, vector& stones, int idx) {
visited[idx] = 1;
for (int i = 0; i < stones.size(); i++) {
if (!visited[i] && areSameGroup(stones[idx], stones[i])) {
dfs(visited, stones, i);
}
}
}
// Main function to find the maximum number of stones that can be removed
int removeStones(vector& stones) {
int numStones = stones.size();
vector visited(numStones, 0);
int groups = 0;
// Iterate over each stone and perform DFS if it's not visited
for (int i = 0; i < numStones; i++) {
if (!visited[i]) {
groups++;
dfs(visited, stones, i);
}
}
// The maximum number of stones that can be removed is total stones minus the number of groups
return numStones - groups;
}
};

[@MP-ny3ep]

Beautiful explanation bro

[@codeby_naruto]

Thank you ❤️❤️

[@shubhamjaiswal7645]