[leetcode] 847. Shortest Path Visiting All Nodes : https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/

[fail-UnionFind]Shortest Path Visiting All Nodes.cc

class Solution {
public:

vector<int> p = vector<int>();
vector<int> d = vector<int>();
    
int Find(int n)
{
	if (p[n] == n) return n;
	p[n] = Find(p[n]);
	return p[n];
}

int Union(int a, int b)
{
	a = Find(a);
	b = Find(b);
	if (a == b)//같은 그룹이라면
		return -1;
	p[b] = a;
	d[a] += d[b];
	return d[a];
}

int shortestPathLength(vector<vector<int>>& graph) {
	int row = graph.size();
	p = vector<int>(row);
	d = vector<int>(row, 1);
	for (int i = 0; i<row; i++)
		p[i] = i;
	int ans = 0;
	for (int i = 0; i<row; i++) {
		for (int j = 0; j<graph[i].size(); j++) {
			int tmp = Union(graph[i][j], i);
			if (tmp != -1)//합칠 수 있으면
			{
				ans = max(ans, tmp);
			}
		}
	}
	return ans;
}
};