-
Notifications
You must be signed in to change notification settings - Fork 12
/
Copy path14 NOV Most Stones Removed with Same Row or Column
56 lines (44 loc) · 1.54 KB
/
14 NOV Most Stones Removed with Same Row or Column
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
// store same row or col cords index in Rowlist and Collist
unordered_map<int,vector<int>>Rowlist;
unordered_map<int,vector<int>>Collist;
void dfs (int index, vector<bool>&visited, vector<vector<int>>&stones)
{
visited[index] = true;
for(int i=0;i<Rowlist[stones[index][0]].size();i++)
{
if(visited[Rowlist[stones[index][0]][i]])continue;
dfs(Rowlist[stones[index][0]][i],visited,stones);
}
for(int i=0;i<Collist[stones[index][1]].size();i++)
{
if(visited[Collist[stones[index][1]][i]])continue;
dfs(Collist[stones[index][1]][i],visited,stones);
}
}
int removeStones(vector<vector<int>>& stones) {
// total stones
int n = stones.size();
// visited stones track
vector<bool>visited(n,false);
// store same row or col cords index in Rowlist and Collist
for(int i=0;i<n;i++)
{
Rowlist[stones[i][0]].push_back(i);
Collist[stones[i][1]].push_back(i);
}
// count the connected components
int c = 0;
// loop through stones and call DFS for unvisited stones
// and count number of connected components
for(int i=0;i<n;i++)
{
if(visited[i])continue;
dfs(i,visited,stones);
c++;
}
// total stones - no of connected components
return n-c;
}
};