[이취코] 10. 그래프 이론 - C++

1. 크루스칼 알고리즘

정렬돼있어야 함. Parent 자신으로 초기화.

 

1-1. 가중치 없는 크루스칼 알고리즘

#include <iostream>
using namespace std;

int parent[10001];

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

void Union(int a, int b) {
    a = parent[a];
    b = parent[b];

    if (a < b) {
        parent[a] = b;
    }
    else
        parent[b]= a;
}


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

    int v, e, a, b;
    cin >> v >> e;

    for (int i = 1; i <= v; i++) {
        parent[i] = i;
    }

    while (e--) {
        cin >> a >> b;
        if(Find(a)== Find(b))
            cout <<"사이클";
        else Union(a, b);
    }
    return 0;
}

 

1-2. 가중치 있는 크루스칼 알고리즘

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

int parent[10001];

struct Edge {
    int v1, v2;
    int cost;
};

bool cmp(Edge &e1, Edge &e2) {
    if (e1.cost == e2.cost) {
        if (e1.v1 == e2.v1) {
            return e1.v2 < e2.v2;
        }
        return e1.v1 < e2.v1;
    }
    return e1.cost < e2.cost;
}

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

bool Union(int a, int b) {
    a = parent[a];
    b = parent[b];

    if (a != b) {
        parent[a] = b;
        return true;
    }
    return false;
}


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

    vector<Edge> edge;
    int v, e, a, b, c;
    int result = 0, cnt = 0;

    cin >> v >> e;

    for (int i = 1; i <= v; i++) {
        parent[i] = i;
    }

    while (e--) {
        cin >> a >> b >> c;
        edge.push_back({a, b, c});
    }
    sort(edge.begin(), edge.end(), cmp);

    for (auto &ed: edge) {
        int v1 = ed.v1;
        int v2 = ed.v2;
        int cost = ed.cost;

        if (Union(v1, v2)) {
            result += cost;
            cnt += 1;

            if (cnt == v - 1) {
                break;
            }
        }
    }

    cout << result;
    return 0;
}

 

2. 위상 정렬 알고리즘

순환하지 않는 방향 그래프(DAG) 문제 - queue 사용

1. 진입차수가 0인 모든 노드를 큐에 넣음

2. 큐가 빌 때가지 반복

    1) 큐에서 원소 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거

    2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다

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

int v, e;
int indegree[100001];
vector<int> graph[100001];

void topologySort() {
    vector<int> result;
    queue<int> q;

    for (int i = 1; i <= v; i++) {
        if (indegree[i] == 0)
            q.push(i);
    }

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

        result.push_back(now);
        for (auto &i: graph[now]) {
            indegree[i]--;
            if (indegree[i] == 0)
                q.push(i);
        }
    }
    for (int i: result) {
        cout << i << ' ';
    }
}

int main() {
    cin >> v >> e;

    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);

        indegree[b]++;
    }

    topologySort();
}
//7 8
//1 2
//1 5
//2 3
//2 6
//3 4
//4 7
//5 6
//6 4

//결과
//1 2 5 3 6 4 7

 

 

3번 문제. 도시분할계획

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

int parent[10001];

struct Edge {
    int v1, v2;
    int cost;
};

bool cmp(Edge &e1, Edge &e2) {
    if (e1.cost == e2.cost) {
        if (e1.v1 == e2.v1) {
            return e1.v2 < e2.v2;
        }
        return e1.v1 < e2.v1;
    }
    return e1.cost < e2.cost;
}

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

bool Union(int a, int b) {
    a = parent[a];
    b = parent[b];

    if (a != b) {
        parent[a] = b;
        return true;
    }
    return false;
}


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

    vector<Edge> edge;
    int v, e, a, b, c, last;
    int result = 0, cnt = 0;

    cin >> v >> e;

    for (int i = 1; i <= v; i++) {
        parent[i] = i;
    }

    while (e--) {
        cin >> a >> b >> c;
        edge.push_back({a, b, c});
    }
    sort(edge.begin(), edge.end(), cmp);

    for (auto &ed: edge) {
        int v1 = ed.v1;
        int v2 = ed.v2;
        int cost = ed.cost;

        if (Union(v1, v2)) {
            result += cost;
            cnt += 1;
            last = cost; //정렬해놔서 맨 끝에 제거하면 제일 큰 값

            if (cnt == v - 1) {
                break;
            }
        }
    }

    cout << result - last;
    return 0;
}

4번 문제. 커리큘럼

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

#define MAX 501
int in_degree[MAX];
int times[MAX];
vector<int> graph[MAX];
int n, x;

void topologySort() {
    vector<int> result(MAX);
    queue<int> q;

    for (int i = 1; i <= n; i++) {
        result[i] = times[i];
        if (in_degree[i] == 0)
            q.push(i);
    }

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

        for (auto &i: graph[now]) {
            result[i] = max(result[i], result[now] + times[i]);
            in_degree[i]--;
            if (in_degree[i] == 0)
                q.push(i);
        }
    }

    for (int i = 1; i <= n; i++)
        cout << result[i] << "\n";
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> x;
        times[i] = x;

        while (true) {
            cin >> x;
            if (x == -1)
                break;
            in_degree[i]++;
            graph[x].push_back(i);
        }
    }

    topologySort();
    return 0;
}
//5
//10 -1
//10 1 -1
//4 1 -1
//4 3 1 -1
//3 3 -1

//결과값
//10
//20
//14
//18
//17