//
// Created by 高森森 on 2022/2/13.
//

#ifndef LEETCODE_SOLUTION41_H
#define LEETCODE_SOLUTION41_H
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include <numeric>
#include "Solution40.h"

using namespace std;
/*class UnionFind2{
public:
    vector<int>father;//父亲节点
    int n;//节点个数
    vector<int>size;//连通分量数
    vector<int>rank;
public:
    //查询父结点
    UnionFind2(int _n):n(_n),father(_n),size(_n,1)，rank(_n,1){
        //iota函数，令father[i]=i;
        iota(father.begin(),father.end(),0);
    }
    int find(int x){
        if(x==father[x])
            return x;
        else{
            father[x]=find(father[x]);
            return father[x];
        }
    }

    //并查集合并
    void merge(int i,int j){
        int x=find(i);
        int y=find(j);
        if(x!=y){
        if(rank[x]<rank[y]){
        swap(x,y);
         father[y]=x;
         size[x]+=size[y];
         if (rank[x] == rank[y])
         rank[x] += 1;
        }
        }
    }
    bool isConnected(int x,int y){
        x=find(x);
        y=find(y);
        return x==y;
    }
};*/

class Solution41 {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
    //使用dfs计算每个感染源节点可以感染的正常节点个数
    //然后统计每个正常节点可以被哪些感染源节点感染
    //如果正常节点可以被多个感染源感染，那么删除其中一个感染源是无用的，因为该正常节点
    //还会被其他感染源节点感染，不会影响M的导小
    //最后统计一下只被一个感染源感染的正常节点中，感染源节点分别感染了哪些正常节点，取得最大轴
    int n=graph.size();
    vector<int>infectSorce(n);
    sort(initial.begin(),initial.end());
    for(int node:initial){
        infectSorce[node]=1;
    }
    //记录正常节点可以被哪些感染源感染
    vector<vector<int>>infectedBy(n);
    for(int n:initial){
        set<int>infected;
        dfs(graph,infectSorce,infected,n);
        for(int v:infected){
            infectedBy[v].push_back(n);
        }
    }
    //统计只被一个感染源节点感染的正常节点中，感染源节点可以感染的节点个数
    vector<int>count(n,-1);
    for(auto c:infectedBy){
        if(c.size()==1)
            count[c[0]]++;
    }
    int min=-1;
    int ans=initial[0];
    for(int i=0;i<n;i++)
    {
        if(count[i]>min){
            ans=i;
            min=count[i];
        }
    }
    return ans;
    }
    void dfs(vector<vector<int>>&graph,vector<int>&infectSorce,set<int>&infected,int u){
            for(int j=0;j<graph.size();j++){
                if(graph[u][j]==1&&infectSorce[j]==0&&!infected.count(j))
                {
                    infected.insert(j);
                    dfs(graph,infectSorce,infected,j);
                }
            }
    }
    int minMalwareSpread2(vector<vector<int>>& graph, vector<int>& initial) {
        int n=graph.size();
        sort(initial.begin(),initial.end());
        int max=-1;
        int ans=initial[0];
        UnionFind2 unionFind2(n);
        //对于所有的正常集合构建并查集
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++){
                if(!count(initial.begin(),initial.end(),i)&&!count(initial.begin(),initial.end(),j))
                {
                    if(graph[i][j]==1)
                        unionFind2.merge(i,j);
                }
            }
        //infectRoot:记录感染源的个数
        //主要记录连通分量的感染来源个数，只有连通分量的根节点存在值，其他下表为-1
        //如果下标-1 说明不是连通分量分界点
        //如果是-2 说明多个感染源
        //其他值说明该连通分量的单一感染源
        vector<int>infectRoot(n,-1);
            for( int i:initial){
                for(int j=0;j<n;j++)
                {
                    if(count(initial.begin(),initial.end(),j))
                        continue;
                    int fa=unionFind2.find(j);

                    if(infectRoot[j]==-2||graph[i][j]==0)
                        continue;
                    if(infectRoot[fa]==-1){
                            infectRoot[fa]=i;
                        }
                            //如果这个连通分量存在感染源，并且不是i，说明有多个感染源
                        else if(infectRoot[fa]!=i){
                            infectRoot[fa]==-2;
                        }
                    }

                }
        vector<int>infectNum(n,0);
        for(int i=0;i<n;i++){
            if(infectRoot[i]==-1||infectRoot[i]==-2)
                continue;
            infectNum[infectRoot[i]]+=unionFind2.size[i];
        }
        for(int i:initial){
            if(infectNum[i]>max)
            {
                max=infectNum[i];
                ans=i;
            }
        }
        return ans;

    }
};


#endif //LEETCODE_SOLUTION41_H