[백준] 22954 - 그래프 트리 분할

https://www.acmicpc.net/problem/22954

22954번: 그래프 트리 분할

 

이 문제를 처음 봤을 때 당연히 그래프가 하나가 주어진다고 생각했다.

하지만 몇 번의 WA 끝에 여러 개의 그래프가 주어질 수 있다고 판단했고, 그게 맞았다.

 

그래서 처음 주어지는 그래프의 수에 따라 구성적으로 설계해 보자.

처음 주어지는 그래프의 수가 3개 이상

이 경우는 이미 3개 이상의 요소들이 있기 때문에 절대 답이 될 수 없다.

처음 주어지는 그래프의 수가 2개

이 경우, 각 그래프 요소의 정점의 개수가 같다면 절대 답이 될 수 없다.

하지만 정점의 개수가 다르다면 간선만 제거해 트리로 만들면 된다.

처음 주어지는 그래프의 수가 1개

그래프의 간선을 몇 개 제거해 두 개의 트리로 만들어야 한다.

그런데 문제에서 각각의 트리는 하나 이상의 정점만 가지고 있으면 된다고 했으므로,

하나의 그래프를 트리로 만들었을 때 리프 노드 하나를 떨어트리면 될 것 같다.

 

처음에는 주어지는 간선을 보고 kruskal, prim 등의 트리 생성 알고리즘을 이용해서 트리를 만들고 리프 노드를 끊을까도 생각했지만, 굳이 그렇게 하지 않아도 된다. 즉, 그래프에서도 트리와 유사한 형태로 리프를 찾을 수 있다.

바로 방문 배열을 만들어서 dfs 내의 for문을 한 번이라도 돌지 않으면, 해당 노드가 리프 노드인 것이다.

 

이후 그래프가 만들어졌을 때 두 그래프의 크기가 같을 경우만 예외처리 해주면 된다.

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<vector<pair<int, int>>> v;
int vis[100001];
vector<int> e[100001];
vector<int> component[100001];
bool isLeaf[100001];
int leaf, componentIdx;

void findLeaf(int now)
{
	leaf = now;
	vis[now] = 1;
	for (auto &i : v[now])
	{
		if (!vis[i.first])
		{
			findLeaf(i.first);
		}
	}
}

void dfs(int now)
{
	component[componentIdx].push_back(now);
	vis[now] = 1;
	bool l = true;
	for (auto &i : v[now])
	{
		if (!vis[i.first])
		{
			e[componentIdx].push_back(i.second);
			l = false;
			dfs(i.first);
		}
	}
	isLeaf[now] = l;
}

void p(vector<int> g)
{
	for (auto &i : g)
	{
		cout << i << ' ';
	}
	cout << '\n';
}

int main()
{
	int n, m;
	cin >> n >> m;
	v.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back({b, i + 1});
		v[b].push_back({a, i + 1});
	}
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i])
		{
			dfs(i);
			componentIdx++;
		}
	}
	if (componentIdx >= 3)
	{
		cout << -1;
		return 0;
	}
	if (componentIdx <= 1)
	{
		int a = 0, b = 0;
		for (int x : component[0])
		{
			if (isLeaf[x])
			{
				a = x;
			}
			else
			{
				b = x;
			}
		}

		component[0].clear();
		e[0].clear();
		memset(vis, 0, sizeof(vis));
		vis[a] = 1;
		componentIdx = 0;
		dfs(b);

		component[1].push_back(a);
	}

	if (component[0].size() == component[1].size())
	{
		cout << -1;
		return 0;
	}

	cout << component[0].size() << ' ' << component[1].size() << '\n';
	p(component[0]);
	p(e[0]);
	p(component[1]);
	p(e[1]);
}