Interview Prepartion
Let me clarify the question once ...\ntestcase\nconstraints :\nn == graph.length\nn == graph[i].length\n2 <= n <= 300\ngraph[i][j] is 0 or 1.\ngraph[i][j] == gr
Let me clarify the question once ...\ntestcase\nconstraints :\nn == graph.length\nn == graph[i].length\n2 <= n <= 300\ngraph[i][j] is 0 or 1.\ngraph[i][j] == graph[j][i]\ngraph[i][i] == 1\n1 <= initial.length < n\n0 <= initial[i] <= n - 1\nAll the integers in initial are unique.\nGive me a few minutes to think it through\ncomment - BF, optimal\ncode\n\n# Intuition\ngraph - Union find\n\n# Approach\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> parent;\n    int find(int node) {\n        if(parent[node] != node) {\n            return parent[node] = find(parent[node]);\n        }\n        return parent[node];\n    }\n    void Union(int u, int v) {\n        int rootu = find(u);\n        int rootv = find(v);\n        if(rootu != rootv) {\n            parent[rootu] = rootv;\n        }\n    }\n    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {\n        int n = graph.size();\n        parent.resize(n);\n        for(int i=0; i<n; i++) {\n            parent[i] = i;\n        }\n        vector<int> clean;\n        set<int> initialSet(initial.begin(), initial.end());\n        for(int i=0; i<n; i++) {\n            if(!initialSet.count(i)) {\n                clean.push_back(i);\n            }\n        }\n        for(auto i: clean) {\n            for(auto j: clean) {\n                if(i != j && graph[i][j]) {\n                    Union(i, j);\n                }\n            }\n        }\n        vector<int> area(n, 0);\n        for (auto i : clean) {\n            area[find(i)]++;\n        }\n        \n        map<int, set<int>> infect_node;\n        map<int, int> infect_count;\n        for (auto i : initial) {\n            for (auto j : clean) {\n                if (graph[i][j]) {\n                    infect_node[i].insert(find(j));\n                }\n            }\n            for (auto j : infect_node[i]) {\n                infect_count[j] += 1;\n            }\n        }\n        int res = initial[0], max_cnt = -1;\n        for (auto& [malware, nodes] : infect_node) {\n            int count = 0;\n            for (auto& node : nodes) {\n                if (infect_count[node] == 1) {\n                    count += area[node];\n                }\n            }\n            if (count > max_cnt || (count >= max_cnt && malware < res)) {\n                max_cnt = count;\n                res = malware;\n            }\n        }\n        return res;\n    }\n};\n```
['C++']