1432번: 그래프 수정

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

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n, ind[300], res[300];
vector<int> adj[300];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0, x; j < n; j++) {
            scanf("%1d", &x);
            if (x) adj[j].push_back(i), ind[i]++;
        }
    }
    priority_queue<int> pq;
    for (int i = 0; i < n; i++) if (!ind[i]) pq.push(i);
    int m = n;
    while (!pq.empty()) {
        int h = pq.top();
        pq.pop();
        res[h] = m--;
        for (auto it : adj[h])
            if (!--ind[it]) pq.push(it);
    }
    if (m) puts("-1");
    else for (int i = 0; i < n; i++) printf("%d ", res[i]);
    return 0;
}

2534번: 카드 배열

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


$O(n\lg n)$

#include<cstdio>
#include<queue>
#include<vector>
#define mod 1000000007
using namespace std;
const int MXN = 3e5;
int n, k, p, ind[2][MXN], r[2][MXN], s, od[MXN];
vector<int> adj[2][MXN];
priority_queue<int> pq;
void f(int t) {
    for (int i = 0; i < k; i++) if (!ind[t][i]) pq.push(-i);
    int i = 0;
    while (!pq.empty()) {
        int h = -pq.top();
        pq.pop();
        r[t][h] = od[i++];
        for (auto it : adj[t][h]) if (!--ind[t][it]) pq.push(-it);
    }
}
int main() {
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 0, x, y; i < p; i++) {
        scanf("%d%d", &x, &y);
        adj[0][x].push_back(y);
        adj[1][y].push_back(x);
        ind[0][y]++;
        ind[1][x]++;
    }
    for (int i = 0; i < k; i++) od[i] = k - 1 - i;
    f(0);
    for (int i = 0; i < k; i++) od[i] = n - k + i;
    f(1);
    for (int i = k; i--;) s = ((long long)s*n + r[1][i] - r[0][i] + mod) % mod;
    printf("%d", s);
    return 0;
}

1766번: 문제집

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


$O(m+n\lg n)$

위상정렬을 할 때, indegree가 0이면서 가장 작은 번호의 문제를 먼저 푼다.

#include<cstdio>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
const int MXN = 32e3;
int n, m, x, y, ind[MXN + 1];
vector<int> adj[MXN + 1];
priority_queue<int, vector<int>, greater<int> > pq;
int main() {
    for (scanf("%d%d", &n, &m); m--;) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        ind[y]++;
    }
    for (int i = 1; i <= n; i++) if (!ind[i]) pq.push(i);
    while (!pq.empty()) {
        int h = pq.top();
        pq.pop();
        printf("%d ", h);
        for (auto it : adj[h]) if (!--ind[it]) pq.push(it);
    }
    return 0;
}

1005번: ACM Craft

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


$O(n)$

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_N = 1e3;
int t, n, m, w, s[MAX_N + 1], ck[MAX_N + 1];
vector<int> adj[MAX_N + 1];
int dfs(int h) {
    if (ck[h]) return s[h];
    ck[h] = 1;
    int maxi = 0;
    for (auto it : adj[h]) maxi = max(maxi, dfs(it));
    return s[h] += maxi;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", s + i), adj[i].clear(), ck[i] = 0;
        for (int i = 0, x, y; i<m; i++) scanf("%d %d", &x, &y), adj[y].push_back(x);
        scanf("%d", &w);
        printf("%d\n", dfs(w));
    }
    return 0;
}