[BOJ-1325]효율적인해킹

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

컴퓨터 대수 그리고 컴퓨터들의 관계 수가 주어지고

관계 수 만큼 A B 가 주어진다.

A가 B를 신뢰하면 B를 해킹할 때, A도 해킹이 가능하다.

이때 최대로 해킹이 가능한 컴퓨터를 보여주면 된다.

여러 대일 경우 오름차순으로 보여준다.

[문제풀이]

우선 해킹가능한 컴퓨터들의 관계를 만들기 위해서 vector를 사용한다.

그리고 컴퓨터들을 순회하기 위해서 BFS 탐색을 실시한다.

그런 후 해킹가능 한 최대 컴퓨터 개수가 나타난다면 answer를 위한 minheap에 컴퓨터를 넣는다.

최대 컴퓨터 개수가 같다면 minheap에 또 넣어준다.

만약 현재 최대컴퓨터해킹가능 개수가 나타나면 minheap을 비워주고, 새로 값을 넣어준다.

vector, queue, heap 을 모두 구현해보기 적절한 문제.

[C++ source code]

#include<iostream>
 
struct mvector {
    int *data;
    int capacity, sz;
 
    mvector(int init_size = 64) {
        data = new int[init_size];
        capacity = init_size;
        sz = 0;
        for (int i = 0; i < init_size; ++i) data[i] = 0;
    }
    void push_back(int input) {
        if (full()) {
            int *temp = new int[capacity];
            for (int i = 0; i < sz; ++i) {
                temp[i] = data[i];
            }
            delete[] data;
            capacity <<= 1;
            data = new int[capacity];
            for (int i = 0; i < sz; ++i) {
                data[i] = temp[i];
            }
            delete[] temp;
        }
        data[sz++] = input;
    }
    int operator[](int i) { return data[i]; }
    int size() { return sz; }
    bool empty() { return !sz; }
    bool full() { return capacity == sz; }
};
 
struct queue {
    int d[1 << 18];
    int s, e;
    queue() { s = e = 0; }
    bool empty() { return s == e; }
    bool full() { return (e + 1) % (1 << 18) == s; }
    void push(int i) {
        if (full()) return;
        d[e++] = i;
        e %= (1 << 18);
    }
    void pop() {
        if (empty()) return;
        s = (s + 1) % (1 << 18);
    }
    int front() {
        if (empty()) return -1;
        return d[s];
    }
};
 
struct minheap {
    int d[1 << 18];
    int e;
    minheap() { e = 0; }
    bool empty() { return e == 0; }
    bool full() { return (e + 1) == (1 << 18); }
    void push(int i) {
        if (full()) return;
        d[++e] = i;
        int cur = e;
        while (cur / 2 > 0) {
            if (d[cur] < d[cur / 2]) swap(d[cur], d[cur / 2]);
            else break;
            cur = cur / 2;
        }
    }
    void pop() {
        if (empty()) return;
        d[1] = d[e];
        e--;
        int cur = 1;
        while (2 * cur <= e) {
            int child;
            if (2 * cur + 1 > e) {
                child = 2 * cur;
            }
            else {
                child = (d[2 * cur] < d[2 * cur + 1]) ? 2 * cur : 2 * cur + 1;
            }
 
            if (d[cur] < d[child]) break;
            swap(d[cur], d[child]);
            cur = child;
        }
    }
    int top() {
        if (empty()) return -1;
        return d[1];
    }
    void swap(int& a, int& b) {
        int t = a;
        a = b;
        b = t;
    }
    void clear() { e = 0; }
};
 
mvector com[10101];
int vis[10101];
queue Q;
minheap ansPQ;
int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        // if b is hacking, a-hacking is possible;
        com[b].push_back(a);
    }
    int mx = 0;
    for (int i = 1; i <= N; ++i) {
        for (int vi = 1; vi <= N; ++vi) vis[vi] = false; // init
        int tmp_mx = 0;
        Q.push(i);
        vis[i] = true;
        while (!Q.empty()) {
            int h = Q.front();
            Q.pop();
            tmp_mx++;
            for (int hi = 0; hi < com[h].sz; ++hi) {
                int t = com[h][hi];
                if (vis[t]) continue;
                vis[t] = true;
                Q.push(t);
            }
        }
        if (mx < tmp_mx) {
            mx = tmp_mx;
            ansPQ.clear();
            ansPQ.push(i);
        }
        else if (mx == tmp_mx) {
            ansPQ.push(i);
        }
    }
 
    while (!ansPQ.empty()) {
        printf("%d ", ansPQ.top());
        ansPQ.pop();
    }
    puts("");
    return 0;
}