[백준/BOJ] 백준 17398번 : 통신망 분할

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

17398번: 통신망 분할

어떤 간선이 제거가 될지 알고 있으므로 제거가 안 되는 간선들은 일단 연결한 뒤 마지막으로 잘라지는 간선부터 확인하고 연결하는 방식으로 문제를 해결했다.

 

코드

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

int n, m, q;
vector<int> parent(100001);
vector<int> rank_size(100001);
vector<int> node_size(100001); //해당 그룹에 정점들이 몇개 있는지 저장
vector<pair<int, int>> edge;
vector<int> cut_check(100000, 0); //제거하는 간선은 1로 표시
vector<int> cut; //제거할 간선의 번호
long long result = 0;

void Pre()
{
	for (int i = 1; i <= 100000; i++)
	{
		parent[i] = i;
		rank_size[i] = 1;
		node_size[i] = 1;
	}
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;

	if (rank_size[u] < rank_size[v])
	{
		parent[u] = v;

		node_size[v] += node_size[u];
	}

	else
	{
		parent[v] = u;

		node_size[u] += node_size[v];

		if (rank_size[u] == rank_size[v])
			rank_size[u]++;
	}
}



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

	Pre();

	cin >> n >> m >> q;

	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		edge.push_back(make_pair(x, y));
	}

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

		cut.push_back(a - 1);
		cut_check[a - 1] = 1;
	}

	//제거가 안되는 간선은 일단 연결한다
	for (int i = 0; i < m; i++)
	{
		//제거할 간선일때
		if (cut_check[i] == 1)
		{
			continue;
		}

		int u = edge[i].first;
		int v = edge[i].second;

		Merge(u, v);
	}

	//마지막으로 잘라지는 간선부터 확인하고, 연결한다
	for (int i = cut.size() - 1; i >= 0; i--)
	{
		int u = edge[cut[i]].first;
		int v = edge[cut[i]].second;

		//u가 속한 그룹과 v가 속한 그룹이 다른 그룹일때
		//(u와v를 연결하는 간선을 제거하면 망이 나눠지는 경우)
		if (Find(u) != Find(v))
		{
			result += (long long)(node_size[Find(u)] * node_size[Find(v)]);

			//연결
			Merge(u, v);
		}
	}

	cout << result << "\n";

	return 0;
}