[C++] Graph | Thought Process
Thought Process in Brief: \n\nI thought about the relation between any two bombs. It appeared every (bomb1,bom2) pair can be represented with true/false. i.e do
Thought Process in Brief: \n\nI thought about the relation between any two bombs. It appeared every (bomb1,bom2) pair can be represented with true/false. i.e does triggering bomb2 triggers bomb1? So I created a matrix with **(i,j)==true**, if: **j**th bomb triggers **i**th bomb\n\nI thought about triggering every one of them one by one. I was initially thinking in the lines of a 1D dp, which was wrong since the problem can\'t be broked down in smaller subproblem with some function f,z such that: f(n)=z(f(n-1)) *[Think about it]*\n\nObserving the relation i.e. the matrix, it appeared as an adjacency matrix, So the problem must be modelable as a graph with ***bombs as nodes*** and the ***relations as directed edges***. \n\nVoila, it is a question of finding the node from which maximum nodes can be traversed in the connected component. (which can be done using dfs) \n\n\n```\nclass Solution {\npublic:\n    bool inrange(int x1,int y1,int r1,int x2,int y2,int r2){\n        long long int x=abs(x1-x2);\n        long long int y=abs(y1-y2);\n        long long int r=abs(r2);\n        return x*x+y*y<=r*r;\n    }\n    int maximumDetonation(vector<vector<int>>& bombs) {\n        int n=bombs.size();\n        vector<vector<bool>> v(n,vector<bool>(n,false));\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++)\n                if(inrange(bombs[i][0],bombs[i][1],bombs[i][2],bombs[j][0],bombs[j][1],bombs[j][2]))\n                    v[i][j]=true;\n        }\n        int maxi=0;\n        for(int i=0;i<n;i++){\n            vector<int> visited(n,-1);\n            int num=1;\n            if(visited[i]==-1) dfs(v,visited,num,i);\n            maxi=max(maxi,num);\n        }\n        return maxi;\n    }\n    void dfs(vector<vector<bool>>& v,vector<int>& visited,int& num,int cur){\n        visited[cur]=num;\n        for(int i=0;i<visited.size();i++){\n            if(visited[i]==-1 and v[i][cur])\n                dfs(v,visited,++num,i);\n        }\n    }\n};\n```
['Depth-First Search', 'Graph']