fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <unordered_set>
  3.  
  4. using namespace std;
  5.  
  6. struct TreeNode {
  7.     int val;
  8.     TreeNode *left;
  9.     TreeNode *right;
  10.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  11. };
  12.  
  13. void dfs(TreeNode* node, unordered_set<TreeNode*>& visited) {
  14.     if (!node || node->val == 0 || visited.count(node)) return;
  15.  
  16.     visited.insert(node);
  17.  
  18.     dfs(node->left, visited);
  19.     dfs(node->right, visited);
  20. }
  21.  
  22. int countIslands(TreeNode* root) {
  23.     if (!root) return 0;
  24.  
  25.     unordered_set<TreeNode*> visited;
  26.     int islandCount = 0;
  27.  
  28.     function<void(TreeNode*)> traverse = [&](TreeNode* node) {
  29.         if (!node) return;
  30.         if (node->val == 1 && !visited.count(node)) {
  31.             islandCount++;
  32.             dfs(node, visited);
  33.         }
  34.         traverse(node->left);
  35.         traverse(node->right);
  36.     };
  37.  
  38.     traverse(root);
  39.     return islandCount;
  40. }
  41.  
  42. int main() {
  43.     TreeNode* root = new TreeNode(1);
  44.     root->left = new TreeNode(0);
  45.     root->right = new TreeNode(1);
  46.     root->right->left = new TreeNode(1);
  47.     root->right->right = new TreeNode(0);
  48.  
  49.     cout << "Number of islands: " << countIslands(root) << endl; // Output: 2
  50.  
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
10
0 1 1 0 1 0 1 1 1 1
1 2
1 3
2 4
4 5
3 6
3 7
7 8
8 9
8 10
stdout
copy 
Number of islands: 1
https://ideone.com/wles8m
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

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!