Calculating the sizeof subtree in O(n)

PHOTO

Mon Jan 10 2022 06:57:07 GMT+0000 (Coordinated Universal Time)

Saved by @vaibhav_55

		vector g[10001];
          vetor visi(10001,0); 
          vector subtree(10001, 0);

          ll dfs(ll v) {
          
              visi[v] = 1;
              ll curr = 1;
          
              for (ll child : g[v]) {
                  if (visi[child] == 0)
                      curr += dfs(child);
              }
              subtree[v] = curr;
              return curr;
          }
          //here,subtree array will give the size of each node's subtree

Save snippets that work from anywhere online with our extensions

Available in the Chrome Web Store

Get Firefox Add-on

Get VS Code extension

Comments

More like this

Graphs

@vaibhav_55

Dfs No of Connected Components Single source shortest path (on trees) Bipartite Graph test cycle detection in undirected graph Cycle detection in directed graph In-Out time of nodes Diameter of Tree Calculating the sizeof subtree in O(n) Bfs single shortest path using bfs Articulation point 🚩🚩🚩 Bridges in graph 🚩🚩🚩 Topological Sort 🚩🚩🚩 Shortest Path in DAG🚩🚩 Dijkstra Algorithm (single source shortest path)🚩🚩 Primes Algo for MST🚩🚩 Disjoint Set Union🚩🚩🚩 Kruskal's Algorithm for MST 🚩🚩🚩

Browse more snippets >>