<p>You are given a network of <code>n</code> nodes represented as an <code>n x n</code> adjacency matrix <code>graph</code>, where the <code>i<sup>th</sup></code> node is directly connected to the <code>j<sup>th</sup></code> node if <code>graph[i][j] == 1</code>.</p>

<p>Some nodes <code>initial</code> are initially infected by malware. Whenever two nodes are directly connected, and at least one of those two nodes is infected by malware, both nodes will be infected by malware. This spread of malware will continue until no more nodes can be infected in this manner.</p>

<p>Suppose <code>M(initial)</code> is the final number of nodes infected with malware in the entire network after the spread of malware stops. We will remove <strong>exactly one node</strong> from <code>initial</code>.</p>

<p>Return the node that, if removed, would minimize <code>M(initial)</code>. If multiple nodes could be removed to minimize <code>M(initial)</code>, return such a node with <strong>the smallest index</strong>.</p>

<p>Note that if a node was removed from the <code>initial</code> list of infected nodes, it might still be infected later due to the malware spread.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
<strong>Output:</strong> 0
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
<strong>Output:</strong> 0
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
<strong>Output:</strong> 1
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == graph.length</code></li>
	<li><code>n == graph[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 300</code></li>
	<li><code>graph[i][j]</code> is <code>0</code> or <code>1</code>.</li>
	<li><code>graph[i][j] == graph[j][i]</code></li>
	<li><code>graph[i][i] == 1</code></li>
	<li><code>1 &lt;= initial.length &lt;= n</code></li>
	<li><code>0 &lt;= initial[i] &lt;= n - 1</code></li>
	<li>All the integers in <code>initial</code> are <strong>unique</strong>.</li>
</ul>

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define pb push_back 
#define mp make_pair 
#define all(x) (x).begin(),(x).end()
#define allb(x) (x).rbegin(),(x).rend()
#define rep_u(ii, aa, bb) for(int ii = aa; ii < bb; ii++)
#define rep_d(ii, aa, bb) for(int ii = aa; ii >= bb; ii--)
#define ff first
#define ss second
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define ordered_set(type) tree<type, null_type,less_equal<type>, rb_tree_tag,tree_order_statistics_node_update>
#define maxhi(type) priority_queue<type>
#define minhi(type) priority_queue<type,vector<type>,greater<type>>

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<int,int> pi;
typedef pair<int,pair<int,int>> ppi;

void __print(int x) { cout << x; }
void __print(long x) { cout << x; }
void __print(long long x) { cout << x; }
void __print(unsigned x) { cout << x; }
void __print(unsigned long x) { cout << x; }
void __print(unsigned long long x) { cout << x; }
void __print(float x) { cout << x; }
void __print(double x) { cout << x; }
void __print(long double x) { cout << x; }
void __print(char x) { cout << '\'' << x << '\''; }
void __print(const char *x) { cout << '\"' << x << '\"'; }
void __print(const string &x) { cout << '\"' << x << '\"'; }
void __print(bool x) { cout << (x ? "true" : "false"); }
template <size_t N>
void __print(const bitset<N>& x) { cout << x; };

template <typename T>
void __print(const T &x);
template <typename T, typename V>
void __print(const pair<T, V> &x);
template <typename T>
void __print(const T &x);
template <typename T, typename... V>
void _print(T t, V... v);

template <typename T, typename V>
void __print(const pair<T, V> &x) {
    cout << '{';
    __print(x.first);
    cout << ", ";
    __print(x.second);
    cout << '}';
}
template <typename T>
void __print(const T &x) {
    int f = 0;
    cout << '{';
    for (auto &i : x) cout << (f++ ? ", " : ""), __print(i);
    cout << "}";
}
void _print() { cout << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cout << ", ";
    _print(v...);
}

#define dbg(x...)                                                            \
    cout << "[" << __func__ << ":" << __LINE__ - 9 << " [" << #x << "] = ["; \
    _print(x);                                                               \
    cout << endl;

ll modpow(ll a, ll n, ll mod) {ll res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 10; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an array of size 3
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return mod_add(arr[0], 0, b);} //for non prime b (using extended euclid gcd)
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}   // for prime b (using fermat little theorem)
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
bool sortcol(const vector<ll>& v1, const vector<ll>& v2){return v1[1] < v2[1];}
void fastio(){ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
string binary(ll n){return bitset<32>(n).to_string();}

const int maxn = 1e5+10;
vll seive(maxn,1),lpf(maxn,0),hpf(maxn,0),pf,divisors[maxn];
void primes(){seive[0]=0,seive[1]=0;lpf[1]=1;hpf[1]=1;for(int i=2;i*i<=maxn;i++){if(seive[i]){lpf[i]=hpf[i]=i;for(int j=2*i;j<maxn;j+=i){seive[j]=0;hpf[j]=i;if(lpf[j]==0){lpf[j]=i;}}}}}
void primefactors(ll n){while(n>1){ll spf=lpf[n];while(n%spf==0){n=n/spf;pf.pb(spf);}}}
void divisor(){for(int i=2;i*i<=maxn;i++){for(int j=i;j<maxn;j+=i){divisors[j].pb(i);}}}

#define MOD 1e9+7

// *---------------------------------------------------------------------------------------*//
class dsu{
    vector<int> parent,size;
    public:
    dsu(ll n){
        parent.resize(n+1);
        size.resize(n+1,1);
        for(int i=0;i<=n;i++) parent[i]=i;
    }
    int find(int x){
        if(x==parent[x]) return x;
        return parent[x]=find(parent[x]);
    }
    
    void merge(int x,int y){
        int p_x=find(x);
        int p_y=find(y);
        if(p_x==p_y) return ;
        if(size[p_x]<size[p_y]){
            size[p_x]+=size[p_y];
            parent[p_y]=p_x;
        }else{
            size[p_y]+=size[p_x];
            parent[p_x]=p_y;
        }
    }
    int get(int x){
        return size[x];
    }
};
class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n=graph.size();
        dsu ds(n);
        forn(i,n){
            forn(j,n){
                if(graph[i][j]==1) ds.merge(i,j);
            }
        }
        int ans=INT_MAX;
        map<int,int> mp;
        for(auto i:initial){
            mp[ds.find(i)]++;
        }
        int mx=INT_MIN;
        for(auto i:initial){
            if(mp[ds.find(i)]==1){
                int sz=ds.get(ds.find(i));
                if(sz>mx){
                    mx=sz;
                    ans=i;
                }else if(sz==mx){
                    ans=min(ans,i);
                }
            }
        }
        if(ans==INT_MAX) return *min_element(all(initial));
        return ans;



    }
};
  

70465