1325번: 효율적인 해킹

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


$O(nm)$

각 컴퓨터마다 DFS 돌려서 해킹될 컴퓨터를 센다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 1e4;
vector<int> adj[MXN + 1];
int vis[MXN + 1], n, m, x, y, cnt[MXN + 1], res;
void f(int h, int r) {
    if (vis[h] == r) return;
    vis[h] = r;
    for (auto it : adj[h]) f(it, r);
    cnt[r]++;
}
int main() {
    for (scanf("%d%d", &n, &m); m--;) {
        scanf("%d%d", &x, &y);
        adj[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        f(i, i);
        if (res < cnt[i]) res = cnt[i];
    }
    for (int i = 1; i <= n; i++) if (res == cnt[i]) printf("%d ", i);
    return 0;
}

$O(m\lg m+n^2)$

SCC를 구한 다음 DFS를 한다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e4;
int n, m, x, y, vis[MXN + 1], maxi, s, sz, flag[MXN + 1], num[MXN + 1], res[MXN + 1];
vector<int> adj[2][MXN + 1], nadj[MXN + 1], v, tv;
void f(int h, int t) {
    if (vis[h] ^ t) return;
    vis[h] = !t;
    for (auto it : adj[t][h]) f(it, t);
    v.push_back(h);
}
void g(int h, int t) {
    if (vis[h] == t) return;
    vis[h] = t;
    for (auto it : nadj[h]) g(it, t);
    s += num[h];
}
int main() {
    for (scanf("%d%d", &n, &m); m--;) {
        scanf("%d%d", &x, &y);
        adj[0][y].push_back(x);
        adj[1][x].push_back(y);
    }
    for (int i = 1; i <= n; i++) f(i, 0);
    tv = v;
    for (int i = tv.size(); i--;) if (vis[tv[i]]) {
        v.clear();
        f(tv[i], 1);
        num[++sz] = v.size();
        for (auto h : v) for (auto t : adj[1][h]) if (flag[t]) nadj[flag[t]].push_back(sz);
        for (auto it : v) flag[it] = sz;
    }
    for (int i = 1; i <= sz; i++) {
        sort(nadj[i].begin(), nadj[i].end());
        nadj[i].erase(unique(nadj[i].begin(), nadj[i].end()), nadj[i].end());
    }
    for (int i = 1; i <= sz; i++) {
        s = 0;
        g(i, i);
        for (int j = 1; j <= n; j++) if (flag[j] == i) res[j] = s;
        maxi = max(maxi, s);
    }
    for (int i = 1; i <= n; i++) if (maxi == res[i]) printf("%d ", i);
    return 0;
}