图论专题训练

leecode 547 并查集

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {ini();int len = isConnected.size();for(int i=0;i<len;i++){for(int j=0;j<len;j++)if(isConnected[i][j]){unio(i,j);}}int ans = 0;for(int i=0;i<len;i++){if(fa[i]==i) ans++;}return ans;}void ini(){for(int i=0;i<=200;i++){fa[i] = i;}}int find(int x){if(x==fa[x]) return x;fa[x] = find(fa[x]);return fa[x];}void unio(int x,int y){int xx = find(x),yy=find(y);if(xx==yy) return;fa[xx] = yy;}int fa[205];
};