<UnionFind> 경로 연결 문제

현재 연결되어 있는 경로 path

수리 해야할 경로 repair

cost 비용 수리떄 들어가는 비용 

수리되면 모든 경로가 이어져야함 단. 수리 경로를 전부 확인하였으나 경로가 전부 연결이 되지 않는다면 cost는 -1로 반환 

 

ex) path [2,1],[3,5],[4,2],[5,6] // [노드1, 노드2]....

ex) repair[3,2,10],[4,5,15] // [노드1,노드2,cost].... 

Inpudata에 데이터 입력 

결과: 10 

#include<iostream>
#include<vector>
using namespace std;
vector<int>tmp;
vector<vector<int>> path;
vector<vector<int>> repair;
void InputData()
{
	/*input data*/
}
int Find(int x, int parent[])
{
	if (parent[x] == x) {

		return x;
	}
	else {
		return Find(parent[x],parent);
	}
 }
void Union(int x, int y, int parent[])
{
	x = Find(x,parent);
	y = Find(y, parent);
	parent[y] = x;
}


int FindPath(int x, int parent[])
{
	if (parent[x] == x)
	{
		return 1;
	}
	else
	{
		return FindPath(parent[x], parent);
	}
}
bool FindPath(int x, int y, int parent[], int datas[], int index )
{
	x = Find( x, parent );//1 ->4 t //2->1->4 //3->3 t//4->4 //5->3 // 6->3
	y = Find( y, parent );//4 ->4 t //1->4->4 //3->3 t//4->4//5->3  // 3->3
	
	if ( x == y )
	{
		datas[ index ] = y;
		return true;
	}
	return false;
}
int main()
{
	int* parent = new int[7];
	int* datas = new int[7];
	int cost = -2;
    //path and repair data input 
	InputData();
    
	for (vector< vector < int > >::iterator it = repair.begin(); it != repair.end(); ++it)
	{
		for (int i = 0; i < 7; ++i)
		{
			parent[i] = i;
			datas[i] = i;
		}
		for (vector< vector < int > >::iterator its = path.begin(); its != path.end(); ++its)
		{
			Union(its->front(), its->back(), parent);//path
		}
		Union(it->front(), it->front() + 1, parent); //repair
		
		for (int i = 1; i < 7; ++i)
		{
			FindPath(i, parent[i], parent, datas, i);
		}
		int answer = 1;
		for (int i = 1; i < 7; ++i)
		{
			if ( datas[1] == datas[i] )
			{
				answer++;
			}
			else
			{
				cost = -1;
			}
			cout << datas[i] << ",";
		}
		
		if ( answer >= 6 )
		{
			if ( cost > it->back() || cost == -2 )
			{
				cost = it->back();
			}
		}
		
		cout << endl;

	}
	cout << "mini cost:" << cost;
	delete[] datas;
	delete[] parent;
	
	system("pause");
	return 0;
}