fork(3) download
copy 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. bool inRange(int i, int j, int m, int n){
  8. 	return i>=0 && i<m && j>=0 && j<n ;
  9. }
  10.  
  11. void dfs(const vector< vector<int> >& v , vector< vector<bool> >& mark,  int m, int n, int i, int j){
  12. 	if(!inRange(i,j,m,n) || mark[i][j])
  13. 		return;
  14.  
  15. 	if( v[i][j]==1){
  16. 		mark[i][j]=true;
  17. 		dfs(v, mark, m, n, i-1, j);
  18. 		dfs(v, mark, m, n, i, j-1);
  19. 		dfs(v, mark, m, n, i+1, j);
  20. 		dfs(v, mark, m, n, i, j+1);
  21. 	}	
  22. }
  23.  
  24.  
  25. int getConnectedCount(const vector< vector<int> >& v , int m, int n){
  26.  
  27. 	int count=0;
  28. 	vector< vector<bool> > mark(m, vector<bool>(n, false));
  29. 	for (int i = 0; i < m; ++i){
  30. 		for(int j=0; j<n; ++j){
  31. 			if(v[i][j]==1 && !mark[i][j]){
  32. 				dfs(v, mark,m, n, i, j);
  33. 				count++;
  34. 			}	
  35. 		}
  36. 	}
  37. 	return count;
  38. }
  39.  
  40.  
  41. int main(int argc, char const *argv[])
  42. {
  43. 	vector< vector<int> > a =
  44. 	{
  45. 	    {1,0,1},
  46. 	    {0,1,0},
  47. 	    {1,1,1}
  48. 	};
  49.  
  50. 	vector< vector<int> > b =
  51. 	{
  52. 	    {1,1,1},
  53. 	    {0,0,1},
  54. 	    {1,1,1}
  55. 	};
  56.  
  57.  
  58. 	vector< vector<int> > c =
  59. 	{
  60. 	    {1,1,1,1,1,1,1,1,1,1,1,1},
  61. 	    {0,0,0,0,0,0,0,0,0,0,0,1},
  62. 	    {1,1,1,0,0,0,0,0,0,0,0,1},
  63. 	    {1,0,0,0,0,0,1,0,0,0,0,1},
  64. 	    {1,0,0,0,0,0,0,0,0,0,0,1},
  65. 	    {1,0,0,0,0,0,0,0,0,0,0,1},
  66. 		{1,1,1,1,1,1,1,1,1,1,1,1}
  67. 	};
  68.  
  69.  
  70.  
  71. 	cout<<getConnectedCount(a,3,3)<<endl;
  72. 	cout<<getConnectedCount(b,3,3)<<endl;
  73. 	cout<<getConnectedCount(c,7,12)<<endl;
  74. 	return 0;
  75. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
1
2
https://ideone.com/GE3w1N
dfs - count
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!