第15题：省份数量

解题思路：运用并查集，当城市之间有路径时，合并不同省份的城市，当没有路径时，什么也不做。并且，运用按秩合并的方法防止树退化成线性表，即总是让秩较小的根节点插入到秩较大的根节点处。

源代码：

class Solution {

public:

    int findCircleNum(vector>& isConnected) {

int n=isConnected.size();

        int ans=n;//初始，所有城市均在不同省份

        vector parents(n,-1);

        vector rank(n,0);

        for(int i=0;i

            for(int j=i+1;j

                if(isConnected[i][j]==1&&UnionSet(i,j,parents,rank)){ //发现两城市属于同一省份，ans--

                    ans--;

                }

            }

        }

        return ans;

    }

    int FindRoot(const vector &parents,int i){

        if(parents[i]==-1) return i;

        return FindRoot(parents,parents[i]);

    }

    bool UnionSet(int a,int b,vector &parents,vector &rank){

        int root_a=FindRoot(parents,a);

        int root_b=FindRoot(parents,b);

        if(root_a==root_b) return false;

        if(rank[root_a]>rank[root_b]) parents[root_b]=root_a;

        else if(rank[root_b]>rank[root_a]) parents[root_a]=root_b;

        else{

            parents[root_b]=root_a;

            rank[root_a]++;

        }

        return true;

    }

};

运行结果：