Articulation Points | Tarjan Algo | beats 89%
Intuition
Run Articulation point algorithm to find out all the articulation points.
During Articulation point algorithm, it also tells us which DFS subtree woul
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
1. Run Articulation point algorithm to find out all the articulation points.
2. During Articulation point algorithm, it also tells us which DFS subtree would get disconnected from the graph if we were to remove this node.
3. We can use this information to solve our problem.
4. If that subtree does not contain any other initially infected nodes, then it is clear that removing this node is going to save that entire subtree otherwise it doesn’t matter.
5. It means, we need to do extra (apart from the usual stuff for Tarjan’s algo) is to make DFS method return the size of the connected component when there are no infected nodes in it otherwise 0.


# Approach
<!-- Describe your approach to solving the problem. -->
At the crucial step of finding articualtion points `id[from] <= low[to]` add the answer we get for `DFS(to)`, coz it will be the number of `UNINFECTED` nodes from `to`. And hence the size pile up in the size array which is `deg` in my code. Finally Arrange the initial values in accordance with the `deg` array.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(V+E)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int dfs(int i, int parent, vector<bool>& vis, vector<vector<int>>& graph, vector<int>& ids, int& out_edges,
    vector<int>& low, int& id, vector<bool>& infected, int& root , vector<int>& deg){
        
        if(parent == root){out_edges++;}

        ids[i] = id;
        low[i] = id;
        id++;
        vis[i] = true;
        // cout<<"dfs at node: "<<i<<endl;
        // conn[i] = comp;
        int count=1;
        bool is_infected = infected[i];

        for(int nx=0; nx < graph.size(); nx++){

            if(graph[i][nx] == 0 || i == nx){continue;}
            
            if( nx == parent){continue;}
            
            if(vis[nx]){
                low[i] = min(low[i], ids[nx]);
                // cout<<"   VISITED nx node is: "<<nx<<endl;
            }else{
                // cout<<"   nx node is: "<<nx<<endl;
                int s = dfs(nx, i, vis, graph, ids, out_edges, low, id, infected, root, deg);
                low[i] = min(low[i], low[nx]);

                if(s==0){
                    is_infected = true;
                }else{
                    count += s;
                }

                if(ids[i] <= low[nx]){
                    deg[i] += s;
                }
            }
        }

        if(is_infected){return 0;}

        return count;
    }

    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();

        vector<int> ids(n);
        vector<int> low(n);

        int id = 0;
        vector<bool> vis(n,false);
        vector<bool> infected(n, false);
        vector<int> deg(n, 0);
        for(int i =0;i<initial.size();i++){
            infected[initial[i]] = true;
        }

        for(int i=0; i<initial.size(); i++){
            int u = initial[i];

            if(!vis[u]){
                int out_edges = 0;
                int u_size = dfs(u, -8, vis, graph, ids, out_edges, low, id, infected, u, deg);
            }
        }

        sort(initial.begin(), initial.end(), [&deg](const int& a, const int& b){
            if(deg[a] == deg[b]){return a<b;}
            return deg[a] > deg[b];
        });

        for(int i =0;i<initial.size();i++){
            cout<<initial[i]<<" ";
        }

        
        return initial[0];
    }
};
```
['C++']