IOI 2020 Conntcting Supertrees

서브태스크 1: 어떤 정점에서 다른 정점으로 가는 경로가 하나씩인 그래프는 무조건 트리이고, 모든 트리는 이 성질을 만족한다. 따라서 0~1,0~2... 간선을 이어주면 정답이 된다.

서브태스크 2: p[i][j]가 1인 i와 j는 한 포레스트에 있고, 아니면 다른 포레스트에 있는 그래프다. union find를 이용해 모순이 없는지를 파악하고, 모순이 있으면 -1, 모순이 없으면 서브태스크 1과 같은 트리를 만들어주면 된다.

서브태스크 3: 서브태스크 2와 비슷하게 하되, 트리 대신 모든 정점을 잇는 사이클을 만들어주면 된다.

서브태스크 5: 정답은 여러 트리들이 사이클로 이어진 형태로 나타낼 수 있고, 같은 트리에 있으면 p[i][j]가 1, 아니면서 연결되어 있으면 p[i][j]는 2이다. 이런 트리를 만들려면 먼저 p[i][j]가 1인 i와 j를 연결시켜, 모순이 없는지 확인한다. 모순이 없으면 서브태스크 2의 풀이를 이용해 트리를 만들고, 연결된 그룹들을 하나의 정점으로 보고, p[i][j]가 1인 i와 j를 연결시키고, 서브태스크 3의 풀이로 사이클을 만든다.

서브태스크 6: p[i][j]가 3이면 항상 답은 -1임을 증명할 수 있다.

#include "supertrees.h"
#include <vector>
using namespace std;
class uf
{
	int arr[1001];
public:
	void init(int n)
	{
		int i;
		for (i = 0; i < n; i++)
		{
			arr[i] = i;
		}
	}
	int f(int n)
	{
		return arr[n] == n ?n: arr[n] = f(arr[n]);
	}
	int u(int n, int m)
	{
		n = f(n);
		m = f(m);
		if (n == m)
			return 0;
		arr[n] = m;
		return 1;
	}
}tree,cycle;
vector<int>cyclearr[1010];
int construct(std::vector<std::vector<int>> p) 
{
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) 
	{
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	tree.init(n);
	cycle.init(n);
	int i, j;
	for(i=0;i<n;i++)
	{
		for (j = 0; j < n; j++)
		{
			if (p[i][j] == 1)
			{
				if (tree.u(i, j))
				{
					answer[i][j] = 1;
					answer[j][i] = 1;
				}
			}
				
			if (p[i][j] == 3)
				return 0;
		}
	}
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (p[i][j] != 1)
			{
				if (tree.f(i) == tree.f(j))
					return 0;
			}
		}
	}
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (p[i][j] == 2)
				cycle.u(tree.f(i), tree.f(j));
		}
	}
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (p[i][j] != 1&&p[i][j]!=2)
			{
				if (cycle.f(tree.f(i)) == cycle.f(tree.f(j)))
					return 0;
			}
		}
	}
	for (i = 0; i < n; i++)
	{
		if(tree.f(i)==i)
			cyclearr[cycle.f(tree.f(i))].push_back(tree.f(i));
	}
	for (i = 0; i < n; i++)
	{
		if (cyclearr[i].size() > 1)
		{
			if (cyclearr[i].size() == 2)
				return 0;
			int j;
			for (j = 0; j < cyclearr[i].size(); j++)
			{
				if (j == 0)
				{
					answer[cyclearr[i][j]][cyclearr[i][j + cyclearr[i].size() - 1]] = 1;
					answer[cyclearr[i][j + cyclearr[i].size() - 1]][cyclearr[i][j]] = 1;
				}
				else
				{
					answer[cyclearr[i][j]][cyclearr[i][j-1]] = 1;
					answer[cyclearr[i][j - 1]][cyclearr[i][j]] = 1;
				}
			}
		}
	}
	build(answer);
	return 1;
}