1922번-네트워크 연결

문제

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

1922번: 네트워크 연결

---

접근방법

1) 접근 사고

 

2) 시간 복잡도

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int INF = 987654321;
const int MAX = 1002;
int n, m;
int parent[MAX];
 
struct info{
    int cost;
    int start;
    int finish;
};
 
vector<info> edge;
bool operator < (info a, info b)
{넽
    if(a.cost != b.cost)
        return a.cost < b.cost;
    return false;
}
 
int find(int c)
{
    if(parent[c] == c)
        return c;
    else
        return parent[c] = find(parent[c]);
}
 
bool merge(int c, int p)
{
    c = find(c);
    p = find(p);
 
    if(c != p)
        parent[c] = p;
    else
        return false;
 
    return true;
}
 
int main(void)
{
    fastio;
    cin >> n >> m;
 
    for(int i = 1; i <= n; i++)
        parent[i] = i;
 
    for(int i = 0; i < m; i++)
    {
        int start, finish , cost;
        cin >> start >> finish >> cost;
        edge.push_back({cost, start, finish});
    }
 
    sort(edge.begin(), edge.end());
 
    int ret = 0;
    for(auto cur : edge)
    {
        if(merge(cur.start, cur.finish))
            ret += cur.cost;
    }
    cout << ret <<"\n";
}