(并查集 省份数量)leetcode 547

纯套模板

模板

返回之前先让所有的下标找一遍自己的最大祖先
for(auto &t:s)
{
    t=findf(t);
    
}





看蓝桥杯的书和视频
#include <iostream>
#include<vector>
#include<queue>
#include<unordered_map>
using namespace std;
const int N = 1e4;
int s[N];
//一般的下标都是从0开始的，所以把根节点改为-1更合适
//可以理解为并查集的根在下面，而树的根在上面
int findf(int i)
{
	if (i == s[i])
		return i;
	else
	{
		return s[i]=findf(s[i]);
	}
}

void andf(int x,int y)
{
	x = findf(x);
	y = findf(y);
	s[x] = y;
}
//每次只改变当前值最大祖先的亲戚关系，这样同时改变了子女的亲戚关系


int main()
{
	int n, m, p;
	cin >> n >> m >> p;
	for (int i = 1;i <= n;i++)
	{
		s[i] = i;
	}
	while (m)
	{
		int x;
		int y;
		cin >> x>> y;
		andf(x, y);

		m--;
	}
	while (p)
	{
		int x, y;
		cin >> x >> y;
		if (findf(x) != findf(y))
			cout << "No" << endl;
		else
			cout << "Yes" << endl;
		p--;
	}


   
	return 0;
}

答案

class Solution {

    vector<int>s;
int findf(int i)
{
	if (s[i] == i)
		return i;
	else
		return s[i] = findf(s[i]);
}

    
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
s = vector<int>(n);
for (int i = 0;i < n;i++)
{
	s[i] = i;
}

for (int j = 0;j < n;j++)
{
	for (int i = 0;i < n;i++)
	{
		if (i == j)
			continue;
		if (isConnected[i][j] == 1&&isConnected[j][i]==1)
		{
			int x = findf(i);
			int y = findf(j);
			isConnected[j][i]=0;
			s[x] = y;	
		}
	}
	
}
for(auto &t:s)
{
    t=findf(t);
    
}
unordered_set<int> ans(s.begin(), s.end());

return ans.size();
    }
};