백준 18133번 가톨릭대학교에 워터 슬라이드를??

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

18133번: 가톨릭대학교에 워터 슬라이드를??

문제를 풀기전에 Disjoint Set와 SCC를 공부해오는 걸 추천드립니다!!

 

풀이

먼저 그래프를 그려볼게요

 

4  3 1  2 2  1 3  1

 

 

1,2번 노드로 가는 통로는 있지만

3,4번으로 가는 통로는 없습니다.

어디에 물을 넣어주던 3,4번에는 각각 물을 넣어줘야됩니다.

 

즉, 자신에게 오는 통로가 없는 노드에 먼저 물을 다 넣어줘야됩니다.

  

하지만 이러한 경우도 존재합니다.

 

 

 

모두 자신에게 오는 경로가 존재합니다. 

그래프끼리 사이클을 형성하는 경우가 존재하기 때문입니다.

잘 생각해보면 사이클을 형성하는 그래프를 하나의 노드로 생각할수 있습니다.

SCC를 이용해 사이클을 찾습니다.

 

 

 

그후 사이클을 형성하는 노드끼리 Disjoint Set으로 묶어 하나의 노드로 먼저 만든 후

다시 자신에게 오는 통로가 없는 노드에 먼저 물을 넣으면 됩니다.

 

 

코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

int N, M;
bool Visit[100001];
vector<int> A[100001];
vector<int> B[100001];
stack<int> STACK;
vector<vector<int>> Group;

int P[100001];
int FindP(int a)
{
	if (P[a] == a)
		return a;
	else
	{
		int emp = FindP(P[a]);
		P[a] = emp;
		return emp;
	}
}

void Union(int a, int b)
{
	P[FindP(b)] = P[FindP(a)];
}

void DFS_A(int n)
{
	Visit[n] = true;
	for (int i = 0; i < A[n].size(); i++)
	{
		int next = A[n][i];
		if (Visit[next])
			continue;
		DFS_A(next);
	}
	STACK.push(n);
}

void DFS_B(int n, vector<int>& SCC)
{
	Visit[n] = true;
	SCC.push_back(n);
	for (int i = 0; i < B[n].size(); i++)
	{
		int next = B[n][i];
		if (Visit[next])
			continue;
		DFS_B(next, SCC);
	}
}

bool ComeNode[100001];

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

	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		A[a].push_back(b);
		B[b].push_back(a);
	}
	for (int i = 1; i <= N; i++)
		P[i] = i;

	for (int i = 1; i <= N; i++)
		if (!Visit[i])
			DFS_A(i);

	memset(Visit, false, sizeof(Visit));

	while (!STACK.empty())
	{
		vector<int> temp;
		int next = STACK.top();
		STACK.pop();
		if (Visit[next])
			continue;
		DFS_B(next, temp);
		Group.push_back(temp);
	}

	for (int i = 0; i < Group.size(); i++)
		for (int j = 1; j < Group[i].size(); j++)
			Union(Group[i][0], Group[i][j]);

	int ans = 0;

	for (int i = 1; i <= N; i++)
		for (int j = 0; j < A[i].size(); j++)
		{
			int a = FindP(i);
			int b = FindP(A[i][j]);
			if (a != b)
				ComeNode[b] = true;
		}

	memset(Visit, false, sizeof(Visit));

	for (int i = 1; i <= N; i++)
	{
		int a = FindP(i);
		if (!Visit[a] && !ComeNode[a])
		{
			DFS_A(a);
			ans++;
		}
	}

	cout << ans << endl;
}

 

-----------------------------------------------------------------------------------------------------------------------------------

질문은 언제나 환영합니다.