package Algorithms_算法.作业.Friend_Enemy_并查集;

public class UnionSet {
    private int []unions,enemy,rank;
    int[][] relations;
    char[] f_or_e;

    public UnionSet(int[][] relations, char[] f_or_e) {
        this.relations = relations;
        this.f_or_e = f_or_e;
    }

    public void init(int n) {
        unions = new int[n+1];
        enemy = new int[n+1];
        rank = new int[n+1];
        for(int i=0;i<=n;i++) {
            unions[i]=i;
            enemy[i]=-1;
            rank[i] = 0;
        }
    }
    public int find(int x) {
        if(unions[x]==x)
            return x;
        else {
            return unions[x] = find(unions[x]);
        }
    }
    public void union(int x,int y){
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        else{
            if(rank[x] < rank[y]){
                unions[x] = y;
            }else{
                unions[y] = x;
                if(rank[x] == rank[y]){
                    ++rank[x];
                }
            }
        }

    }
    public void solve(int n,int m){
        for(int i=0;i<m;i++){
            char c = f_or_e[i];
            int a = relations[i][0],b = relations[i][1];
            if(c=='F'){
                union(a,b);
                System.out.println("合并:"+a+","+b);
            }
            //我没想到的点：敌人的敌人怎么办，我原来想的是，每个集团领导带一个队列，
            // 存放敌人，每一个加入的点把新的敌人加入到领导的敌人队列里
            else{
                if(enemy[a]!=-1){
                    union(enemy[a],b);
                    System.out.println("合并:"+enemy[a]+","+b);
                }
                if(enemy[b]!=-1){
                    union(enemy[b],a);
                    System.out.println("合并:"+enemy[b]+","+a);
                }
                else if(enemy[a]==-1&&enemy[b]==-1){
                    enemy[a]=b;
                    enemy[b]=a;
                }
            }
        }
        int count_g=0;
        for(int i=1;i<=n;i++){
            if(unions[i]==i)
                count_g++;
        }
        System.out.println(count_g);
    }
    public void mySolve(int n,int m){
        for(int i=0;i<m;i++){
            char c = f_or_e[i];
            int a = relations[i][0],b = relations[i][1];
            if(c=='F'){
                union(a,b);
                System.out.println("合并:"+a+","+b);
            }
            //我没想到的点：敌人的敌人怎么办，我原来想的是，每个集团领导带一个队列，
            // 存放敌人，每一个加入的点把新的敌人加入到领导的敌人队列里
            //要用到hashmap
            //来看一下题解的意思：一个人最多只会有一个孤立的敌人
            //因为两个人不是敌人就是朋友
            //如果我有两个敌人，
            //他们是朋友，那记录一个就可以，合并的时候两个会一起合并
            //他们是敌人，敌人的敌人是朋友，与假设矛盾，所以不存在
            //所以无论怎样，我只需要记录一个敌人就可以代表所有敌人
            else{
                if(enemy[a]!=-1){
                    union(enemy[a],b);
                    System.out.println("合并:"+enemy[a]+","+b);
                }
                if(enemy[b]!=-1){
                    union(enemy[b],a);
                    System.out.println("合并:"+enemy[b]+","+a);
                }
                else if(enemy[a]==-1&&enemy[b]==-1){
                    enemy[a]=b;
                    enemy[b]=a;
                }
            }
        }
        int count_g=0;
        for(int i=1;i<=n;i++){
            if(unions[i]==i)
                count_g++;
        }
        System.out.println(count_g);
    }
    public static void main(String[] args) {
        int[][] relations= {
                {1,4},
                {3,5},
                {4,6},
                {1,2}};
        char[] f_or_e = {
                'E',
                'F',
                'F',
                'E'};
        UnionSet demo = new UnionSet(relations,f_or_e);
        demo.init(6);
        demo.solve(6,relations.length);
    }
}