当前位置：网站首页>并查集模板

并查集模板

2022-08-10 07:56:00 【ThXe】

struct DSU {
    
	int dis[N], si[N], f[N];//维护当前节点到根节点的距离，集合大小、
	int n, m;
	void init()
	{
    
		cin >> n;
		for (int i = 1; i <= n; i++)f[i] = i,si[i]=1;
	}
	int find(int x)
	{
    
		if (x != f[x])
		{
       
			int last = f[x];
			f[x] = find(f[x]);
			dis[x] += dis[last];
		}
		return f[x];
	}
	void slove()//最小环、适用于边权为1 且每个点的出度为1
	{
       
		int ans = 0x3f3f3f3f;
		for (int i = 1; i <= n; i++)
		{
    
			int t; cin >> t;
			if (find(i) == find(t))
			{
    
				ans = min(ans, dis[i] + dis[t] + 1);
			}
			else
			{
    
				dis[i] = dis[t] + 1;
				f[find(i)] = find(t);
				si[find(t)] += si[find(i)];
			}
		}
		cout << ans << endl;
	}
}dsu;