[백준/BOJ] 백준 20530번 : 양분

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

20530번: 양분

그래프는 하나의 사이클이 존재하고 해당 사이클에 사이클이 아닌 그래프들이 붙어있는 형태가 된다. 그래서 사이클에 속한 어떤 정점과 연결되어 있는 사이클에 속하지 않는 정점들을 한 그룹으로 하고, 사이클에 속한 각각의 정점들은 다른 그룹으로 하여 그룹을 만들어서 같은 그룹일 때는 단순 경로의 수가 1개, 다른 그룹일 때는 단순 경로의 수가 2개인 것을 이용하여 문제를 해결했다. 사이클에 속해있는 정점을 찾는 방법은, 그래프를 양방향으로 연결하여 indegree가 1인 정점을 계속 지워 나가면 사이클에 속하는 정점들만 남게 된다는 것을 이용했다.

그래프 설명

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, q;
vector<int> adj[200005];
vector<int> visited(200005, 0);
vector<int> cycle_check(200005, 1);
vector<int> group_check(200005, 0);
vector<int> indegree(200005, 0);

//indegree가 1인것을 지워나가면 싸이클에 속하는 정점들만 남는다
void CycleCheck()
{
	queue<int> q;
	for (int i = 1; i <= n; i++)
	{
		if (indegree[i] == 1)
		{
			q.push(i);
		}
	}

	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		visited[here] = 1;
		cycle_check[here] = 0; //해당 정점은 싸이클이 아니다

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];
			indegree[there]--;

			//방문하지 않았고, indegree가 1일때
			if (visited[there] == 0 && indegree[there] == 1)
			{
				q.push(there);
			}
		}
	}
}

void GroupCheck(int here, int group_num)
{
	group_check[here] = group_num;

	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];

		//there가 싸이클 정점일때
		if (cycle_check[there] == 1)
			continue;

		if (group_check[there] == 0)
		{
			GroupCheck(there, group_num);
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> q;

	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;

		adj[a].push_back(b);
		indegree[b]++;

		adj[b].push_back(a);
		indegree[a]++;
	}

	//indegree가 1인것을 제외하는 방법으로 싸이클을 구한다
	CycleCheck();

	for (int i = 1; i <= n; i++)
	{
		//싸이클에 속한 정점일때
		if (cycle_check[i] == 1)
		{
			//해당 정점을 루트로 해서 싸이클에 속하지 않은 정점들을 자식 노드로한 트리로 그룹을 만든다
			GroupCheck(i, i);
		}
	}

	for (int i = 0; i < q; i++)
	{
		int a, b;
		cin >> a >> b;

		if (group_check[a] == group_check[b]) //같은 그룹일때
			cout << 1 << "\n";
		else
			cout << 2 << "\n";
	}

	return 0;
}