Kruskal, Prim 구현

이론은 http://chanhaeng.blogspot.com/2018/09/23-minimum-spanning-trees.html 참조

백준 문제 https://www.acmicpc.net/problem/1922 를 기반으로함.

Macro + Input 방식:

#define intmax 2147483647
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define mp make_pair
#define pii pair<int, int>
#define pipii pair<int, pii>
#define SIZE 1001

int N, M;
struct info
{
 int to;
 int cost;
};

vector<info> graph[SIZE];
int ans;

void TakeInput()
{
 cin >> N >> M;
 REP(i, M)
 {
  int from, to, cost;
  cin >> from >> to >> cost;
  graph[from].push_back({ to, cost });
  graph[to].push_back({ from, cost });
 }
}

Kruskal :

vector<int> whosyaparent;
vector<int> yourRank;
int findP(int index)
{
 if (index != whosyaparent[index])
  whosyaparent[index] = findP(whosyaparent[index]);
 return whosyaparent[index];
}

void unite(int x, int y)
{
 x = findP(x), y = findP(y);
 if (yourRank[x] > yourRank[y])
  whosyaparent[y] = x;
 else
 {
  whosyaparent[x] = y;
  if (yourRank[x] == yourRank[y]) ++yourRank[y];
 }
}

void Kruskal()
// union-by-rank + path compression
{
 whosyaparent = vector<int>(N + 1, 0);
 for (int i = 1; i <= N; ++i)
  whosyaparent[i] = i;

 yourRank = vector<int>(N + 1, 0);

 priority_queue<pipii> pq; // -cost(min), from to 
 FOR(i, 1, N + 1)
 {
  REP(j, graph[i].size())
  {
   info& you = graph[i][j];

   /*
   The reason why I negate the cost is that
   I'd like to make the priority_queue min_heqp priority queue.
   So, Notice that I negate the cost value to use it!
   */
   pq.push(mp(-you.cost, mp(i, you.to)));
  }
 }

 while (pq.empty() == false)
 {
  pipii top = pq.top(); pq.pop();
  int from = top.second.first;
  int to = top.second.second;
  int cost = -top.first;
  
  if (findP(from) != findP(to))
  {
   ans += cost;
   unite(from, to);
  }
 }
}

Prim :

vector<pipii> keyandpi;
vector<bool> visited;
void Prim()
{
 visited = vector<bool>(N + 1, false);
 keyandpi = vector<pipii>(N + 1, mp(-intmax, mp(0, 0))); // key, its index, parent
 REP(i, N + 1) keyandpi[i].second.first = i;

 // start point 1
 keyandpi[1].first = 0;

 priority_queue<pipii> pq;
 FOR(i, 1, N + 1)
  pq.push(keyandpi[i]);

 while (pq.empty() == false)
 {
  pipii top = pq.top(); pq.pop();
  int from = top.second.first;
  
  if (visited[from])
  {
   // the reason why I do this is that
   // the node already visited weight the cost twice.
   // So we have to clear the weight.
   ans = top.first == intmax * -1 ? ans : ans + top.first;
   continue;
  }
  visited[from] = true;

  REP(i, graph[from].size())
  {
   int to = graph[from][i].to;
   int cost = graph[from][i].cost;

   if (visited[to] || cost >= keyandpi[to].first * -1) continue;

   keyandpi[to].first = cost * -1;
   keyandpi[to].second.second = from;
   pq.push(mp(cost * -1, mp(to, from)));
   ans += cost;
  }
  
 }
}