3108번: LOGO

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

겹치는 직사각형 쌍마다 간선을 만들고 분리된 그래프의 개수를 센다.

시간복잡도는 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, s1[1001], e1[1001], s2[1001], e2[1001], vis[1001], cnt;
bool out(int a, int b) {
    return s2[a] < s1[b] || e2[a] < e1[b] || s1[b] < s1[a] && s2[a] < s2[b] && e1[b] < e1[a] && e2[a] < e2[b];
}
void dfs(int h) {
    vis[h] = 1;
    for (int i = 0; i <= n; i++) if (!out(h, i) && !out(i, h) && !vis[i]) dfs(i);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", s1 + i, e1 + i, s2 + i, e2 + i);
        if (s1[i] > s2[i]) swap(s1[i], s2[i]);
        if (e1[i] > e2[i]) swap(e1[i], e2[i]);
    }
    for (int i = 0; i <= n; i++) if (!vis[i]) dfs(i), cnt++;
    printf("%d", cnt - 1);
    return 0;
}

1103번: 게임

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

DAG로 가정해서 DP로 푸는 동시에 사이클이 존재하는지 확인한다.

시간복잡도는 $O(nm)$

#include<cstdio>
#include<algorithm>
using namespace std;
const int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int n, m, dp[50][50], vis[50][50], p[50][50];
char s[50][51];
int f(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= m || s[x][y] == 'H') return 0;
    if (p[x][y]) { puts("-1"); exit(0); }
    int &ret = dp[x][y];
    if (vis[x][y]) return ret;
    p[x][y] = vis[x][y] = 1;
    int t = s[x][y] - '0';
    for (int i = 0; i < 4; i++) ret = max(ret, f(x + t*dx[i], y + t*dy[i]));
    p[x][y] = 0;
    return ++ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", s[i]);
    printf("%d", f(0, 0));
    return 0;
}

2842번: POŠTAR

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

방문한 칸의 최소 높이가 x일 때 메일을 모두 보낼수 있는 방문한 칸의 최대 고도의 최솟값을 f(x)라 하자.
f(x)는 단조증가 함수가 된다. 고로 l=x, r=f(x)로 잡고 inchworm 알고리즘을 적용할 수 있다.
[l,r] 구간의 고도에 해당하는 칸만을 방문하여 모든 메일을 배달할 수 있다면 l++, 그렇지 않다면 r++을 해주며 모든 x에 대한 f(x) 값을 구한다. 답은 이러한 f(x) - x 들 중 최솟값이 된다.

시간복잡도는 $O(n^4)$

#include<cstdio>
#include<algorithm>
using namespace std;
const int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };
int n, a[50][50], vis[50][50], sx, sy, res = 1e9, v[2500], l, r;
char s[50][51];
void f(int x, int y) {
    if (x < 0 || y < 0 || x == n || y == n || vis[x][y] || a[x][y]<v[l] || a[x][y]>v[r]) return;
    vis[x][y] = 1;
    for (int i = 0; i < 8; i++) f(x + dx[i], y + dy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
        for (int j = 0; j < n; j++) if (s[i][j] == 'P') sx = i, sy = j;
    }
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", a[i] + j), v[i*n + j] = a[i][j];
    sort(v, v + n*n);
    while (r < n*n) {
        f(sx, sy);
        int flag = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!vis[i][j] && s[i][j] == 'K') flag = 1;
                vis[i][j] = 0;
            }
        }
        flag ? r++ : res = min(res, v[r] - v[l++]);
    }
    printf("%d", res);
    return 0;
}

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;
}

3264번: ONE

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


$O(n)$

답은 (모든 간선 가중치 합)*2-(s에서 가장 먼 교차점까지의 거리)

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n, s, tot;
vector<pair<int, int> > adj[100001];
int f(int h, int p) {
    int m = 0;
    for (auto it : adj[h]) if (it.first^p) m = max(m, it.second + f(it.first, h));
    return m;
}
int main() {
    scanf("%d%d", &n, &s);
    for (int i = 1, a, b, c; i < n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
        tot += c;
    }
    printf("%d", tot * 2 - f(s, 0));
    return 0;
}

1941번: 소문난 칠공주

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


$O(1)$

25칸 중 7개의 칸을 선택해서 모두 인접해 있고 S가 4개 이상인 경우를 카운트

#include<cstdio>
#include<algorithm>
using namespace std;
char a[5][6];
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int r, vis[5][5], p[25], s, tot;
void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= 5 || y >= 5 || vis[x][y] || !p[x * 5 + y]) return;
    vis[x][y] = 1;
    s += a[x][y] == 'S';
    tot++;
    for (int i = 0; i < 4; i++) dfs(x + fx[i], y + fy[i]);
}
int main() {
    for (int i = 0; i < 5; i++) scanf("%s", a[i]);
    for (int i = 18; i < 25; i++) p[i] = 1;
    do {
        fill(vis[0], vis[5], 0);
        int i = s = tot = 0;
        for (; !p[i]; i++);
        dfs(i / 5, i % 5);
        r += tot == 7 && s > 3;
    } while (next_permutation(p, p + 25));
    printf("%d", r);
    return 0;
}

7981번: 장비를 정지합니다

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

$O(n+\sum r)$

DFS를 활용한 DP로 쉽게 해결할 수 있다.
dp[i]를 i번 장비를 정지시키기 위해 필요한 최소 전력이라고 정의하자.
i번 장비에 약한 충격을 가했을 때 다시켜지는 장비 리스트를 aj라 하면
dp[i]=min(u[i]+sum(dp[aj]),z[i]) 이다.
이렇게 풀다보면 dp[aj]를 구해놓지 않은 경우가 있을 수도 있다.
이런 경우에는 사이클 상의 장비 중 적어도 하나는 강한 충격이 가해질 것이므로 i번 장비에 강한 충격을 가해도 상관없다.
(아래 소스에서는 dp[aj]=z[aj]라고 가정했다.)
사이클 상의 모든 장비가 약한 충격이 가해졌다면 dp값이 무한정 증가하는 모순이 생기기 때문이다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 2e5;
int u[MXN + 1], z[MXN + 1], n, ck[MXN + 1];
vector<int> adj[MXN + 1];
int f(int h) {
    if (!ck[h]) {
        ck[h] = 1;
        long long s = u[h];
        for (auto it : adj[h]) s += f(it);
        if (z[h] > s) z[h] = s;
    }
    return z[h];
}
int main() {
    scanf("%d", &n);
    for (int i = 1, r; i <= n; i++) {
        scanf("%d%d%d", u + i, z + i, &r);
        for (int j = 0, x; j < r; j++) {
            scanf("%d", &x);
            adj[i].push_back(x);
        }
    }
    printf("%d", f(1));
    return 0;
}

1260번: DFS와 BFS

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

$O(n^2)$

DFS, BFS 구현

#include<cstdio>
const int MXN = 1e3;
int adj[MXN + 1][MXN + 1], n, m, s, ck[MXN + 1];
void dfs(int x) {
    if (ck[x]) return;
    ck[x] = 1;
    printf("%d ", x);
    for (int i = 1; i <= n; i++) if (adj[x][i]) dfs(i);
}
int q[MXN], h, t;
void bfs(int x) {
    q[t++] = x;
    ck[x] = 1;
    while (h^t) {
        printf("%d ", q[h]);
        for (int i = 1; i <= n; i++) if (adj[q[h]][i] && !ck[i]) ck[q[t++] = i] = 1;
        h++;
    }
}
int main() {
    scanf("%d %d %d", &n, &m, &s);
    for (int i = 0, x, y; i < m; i++) scanf("%d %d", &x, &y), adj[x][y] = adj[y][x] = 1;
    dfs(s);
    for (int i = 1; i <= n; i++) ck[i] = 0;
    puts("");
    bfs(s);
    return 0;
}

11724번: 연결 요소의 개수

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


$O(n^2)$

#include<cstdio>
int n, m, ck[1001], r, adj[1001][1001];
void dfs(int h) {
    ck[h] = 1;
    for (int i = 1; i <= n; i++) if (adj[h][i] && !ck[i]) dfs(i);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d%d", &x, &y);
        adj[x][y] = adj[y][x] = 1;
    }
    for (int i = 1; i <= n; i++) if (!ck[i]) dfs(i), r++;
    printf("%d", r);
    return 0;
}

1707번: 이분 그래프

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


$O(t(v+e))$

두 가지 색으로 채색이 가능한지 본다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int t, n, m, c[20001], r;
vector<int> adj[20001];
void dfs(int h) {
    for (auto it : adj[h]) {
        if (c[it]) r |= c[it] + c[h] != 3;
        else c[it] = 3 - c[h], dfs(it);
    }
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) adj[i].clear(), c[i] = 0;
        for (int i = 0, x, y; i < m; i++) {
            scanf("%d%d", &x, &y);
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        r = 0;
        for (int i = 1; i <= n; i++) if (!c[i]) c[i] = 1, dfs(i);
        puts(r ? "NO" : "YES");
    }
    return 0;
}

2146번: 다리 만들기

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


$O(n^2)$

섬마다 다르게 표시해놓고 섬의 각 지점을 큐에 넣고 BFS를 돌려 다른 섬간 최단 거리를 구한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int n, b[100][100], d[100][100], c, r = 1e9;
queue<pair<int, int> > q;
void f(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= n || !d[x][y]) return;
    d[x][y] = 0;
    b[x][y] = c;
    q.push({ x,y });
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) scanf("%d", d[i] + j);
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) if (d[i][j]) ++c, f(i, j);
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = x + fx[i], ty = y + fy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= n) continue;
            if (b[tx][ty]) {
                if (b[tx][ty] ^ b[x][y] && r>d[tx][ty] + d[x][y]) r = d[tx][ty] + d[x][y];
                continue;
            }
            b[tx][ty] = b[x][y];
            d[tx][ty] = d[x][y] + 1;
            q.push({ tx,ty });
        }
    }
    printf("%d", r);
    return 0;
}

12004번: Closing the Farm (Silver)

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


$O(n(n+m))$

문제 그대로 구현.
매번 dfs 탐색을 해서 해당 곳간으로 부터 갈 수 있는 곳의 개수와 열린 곳간의 개수가 같은지 보고 해당 곳간을 닫는다.

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int n, m, ck[3001], cls[3001];
vector<int> adj[3001];
int f(int h) {
        if (cls[h] || ck[h]) return 0;
        ck[h] = 1;
        int s = 1;
        for (auto it : adj[h]) s += f(it);
        return s;
}
int main() {
        scanf("%d%d", &n, &m);
        for (int i = 0, x, y; i < m; i++) {
                scanf("%d%d", &x, &y);
                adj[x].push_back(y);
                adj[y].push_back(x);
        }
        for (int i = n, x; i; i--) {
                memset(ck, 0, sizeof(ck));
                scanf("%d", &x);
                puts(f(x) == i ? "YES" : "NO");
                cls[x] = 1;
        }
        return 0;
}

9470번: Strahler 순서

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


$O(tn)$

dfs를 통해 말단 노드에서 거슬러 올라가며 dp를 해준다.

#include<cstdio>
#include<vector>
using namespace std;
int t, k, m, p, dp[1001];
vector<int> adj[1001];
int f(int h) {
        if (dp[h]) return dp[h];
        int ck = 1;
        for (auto it : adj[h]) {
                if (f(it) == dp[h]) ck = 1;
                if (f(it) > dp[h]) {
                        dp[h] = f(it);
                        ck = 0;
                }
        }
        return dp[h] += ck;
}
int main() {
        for (scanf("%d", &t); t--;) {
                scanf("%d%d%d", &k, &m, &p);
                for (int i = 1; i <= m; i++) adj[i].clear(), dp[i] = 0;
                for (int i = 0, x, y; i < p; i++) {
                        scanf("%d%d", &x, &y);
                        adj[y].push_back(x);
                }
                printf("%d %d\n", k, f(m));
        }
        return 0;
}

1029번: 그림 교환

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


$O(n*2^n)$

모든 (그림을 소유했던 사람 집합, 마지막에 그림을 소유한 사람, 마지막 가격) 쌍이 노드로 존재하는 그래프를 탐색한다.

#include<cstdio>
int n, a[15][15], ck[1 << 15][15][10], r;
void f(int x, int y, int z, int c) {
    if (c > r) r = c;
    ck[x][y][z] = 1;
    for (int i = 0; i < n; i++) if (a[y][i] >= z&&!(1 << i&x) && !ck[1 << i | x][i][a[y][i]]) f(1 << i | x, i, a[y][i], c + 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%1d", &a[i][j]);
    f(1, 0, 0, 1);
    printf("%d", r);
    return 0;
}

12745번: Traffic (Small)

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


dfs를 q번 돌게 했더니 시간 초과되었다.
같은 시간 복잡도에서도 상수가 작은 lca 연산으로 해결한다.

$O(nq)$

주어진 그래프를 rooted tree 로 만든다.
(x,y) 쿼리가 들어오면 x와 y를 연결하는 경로상의 간선에 카운트 해준다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 2222;
int n, q, s[MXN + 1], par[MXN + 1], dep[MXN + 1], r;
vector<int> adj[MXN + 1];
pair<int, int> t;
void f(int x) {
    for (auto it : adj[x]) if (it^par[x]) {
        par[it] = x;
        dep[it] = dep[x] + 1;
        f(it);
    }
}
void g(int x, int y) {
    s[x]++;
    pair<int, int> tp = { x,y };
    if (tp.first>tp.second) swap(tp.first, tp.second);
    if (s[x]>r || s[x] == r&&tp<t) {
        r = s[x];
        t = tp;
    }
}
void lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    while (dep[x]>dep[y]) g(x, par[x]), x = par[x];
    while (par[x] ^ par[y]) {
        g(x, par[x]);
        g(y, par[y]);
        x = par[x];
        y = par[y];
    }
    if (x^y) g(x, par[x]), g(y, par[y]);
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1, x, y; i<n; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1);
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        lca(x, y);
    }
    printf("%d %d %d", t.first, t.second, r);
    return 0;
}

12746번: Traffic (Large)

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


$O((n+q)\lg n)$

주어진 그래프를 rooted tree 로 만든다.
(x,y) 쿼리가 들어오면 s[x]++, s[y]++, s[lca(x,y)]-=2를 해주고
루트를 시작점으로 dfs를 돌면서 자식의 s[]를 부모의 s[]에 누적시키면 모든 간선의 방문 수를 알 수 있다.
lca 쿼리를 O(lgn)이 되도록 구현해야 한다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 222222;
int n, q, dp[MXN + 1][18], dep[MXN + 1], s[MXN + 1], r;
vector<int> adj[MXN + 1];
pair<int, int> t;
void f(int x) {
    for (auto it : adj[x]) {
        if (it == dp[x][0]) continue;
        dep[it] = dep[x] + 1;
        dp[it][0] = x;
        for (int i = 1; i<18; i++) dp[it][i] = dp[dp[it][i - 1]][i - 1];
        f(it);
    }
}
void g(int x) {
    for (auto it : adj[x]) if (it^dp[x][0]) {
        g(it);
        pair<int, int> tp = { x,it };
        if (x>it) swap(tp.first, tp.second);
        if (s[it]>r || s[it] == r&&tp<t) {
            r = s[it];
            t = tp;
        }
        s[x] += s[it];
    }
}
int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    for (int i = 17; i >= 0; i--)
        if (dep[x] - dep[y] >= 1 << i) x = dp[x][i];
    if (x == y) return x;
    for (int i = 17; i >= 0; i--)
        if (dp[x][i] ^ dp[y][i]) x = dp[x][i], y = dp[y][i];
    return dp[x][0];
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1, x, y; i<n; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1);
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        s[x]++;
        s[y]++;
        s[lca(x, y)] -= 2;
    }
    g(1);
    printf("%d %d %d", t.first, t.second, r);
    return 0;
}

13265번: 색칠하기

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


$O(t(n+m))$

홀수 개수의 노드로 이루어진 사이클이 존재하면 불가능, 그러한 사이클이 존재하지 않는다면 가능하다.

#include<cstdio>
#include<vector>
using namespace std;
int t, n, m, ck[1001], r;
vector<int> adj[1001];
void f(int h) {
    for (auto it : adj[h]) {
        if (!ck[it]) ck[it] = 3 - ck[h], f(it);
        if (ck[h] == ck[it]) r = 1;
    }
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) adj[i].clear(), ck[i] = 0;
        for (int i = 0, x, y; i<m; i++) {
            scanf("%d%d", &x, &y);
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        r = 0;
        for (int i = 1; i <= n; i++) if (!ck[i]) ck[i] = 1, f(i);
        puts(r ? "impossible" : "possible");
    }
    return 0;
}

11964번: Fruit Feast

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


$O(t)$

dfs를 이용해 flood fill을 한다.

#include<cstdio>
int t, a, b, ck[2][5000001], r;
void f(int x, int y) {
    if (x>t || x>t || ck[y][x]) return;
    ck[y][x]++;
    if (x > r) r = x;
    if (!y) f(x / 2, 1);
    f(x + a, y);
    f(x + b, y);
}
int main() {
    scanf("%d%d%d", &t, &a, &b);
    f(0, 0);
    printf("%d", r);
    return 0;
}

10891번: Cactus? Not cactus?

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

참고로 본래 선인장 그래프의 정의는 '그래프에 속해 있는 모든 간선에 대해 최대 1개의 사이클에 포함된 것'이다.
문제에 제시된 정의는 살짝 다르므로 유의하자.


$O(n+m)$

dfs 탐색을 하다가 이미 방문했던 노드를 탐색하게 된다면 사이클을 이루는 것이다.
이 사이클을 이루는 노드들을 모두 체크해놓자.
이후에 체크된 노드를 다시 탐색하게 된다면 그 노드는 적어도 2개 이상의 사이클에 포함되어 있으므로 선인장 그래프가 아니다.
이러한 노드가 없다면 선인장 그래프이다.

#include<cstdio>
#include<stdlib.h>
#include<vector>
using namespace std;
const int MXN = 1e5;
int n, m, par[MXN + 1], ck[MXN + 1];
vector<int> adj[MXN + 1];
void f(int h) {
    ck[h]++;
    for (auto it : adj[h]) {
        if (it == par[h] || ck[it] == 2) continue;
        if (ck[it]) {
            for (int i = h; i^par[it]; i = par[i])
                if (ck[i]++ == 2) puts("Not cactus"), exit(0);
        }
        else par[it] = h, f(it);
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1);
    puts("Cactus");
    return 0;
}

2583번: 영역 구하기

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


$O(nm+k)$

#include<cstdio>
#include<algorithm>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int a[100][100], m, n, c, r[10000], rcnt;
void f(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= m || a[x][y]) return;
    a[x][y] = 1;
    r[rcnt]++;
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d %d %d", &m, &n, &c);
    for (int i = 0, x, y, z, w; i < c; i++) {
        scanf("%d %d %d %d", &x, &y, &z, &w);
        for (int j = x; j < z; j++) for (int k = y; k < w; k++) a[j][k] = 1;
    }
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (!a[i][j]) f(i, j), rcnt++;
    std::sort(r, r + rcnt);
    printf("%d\n", rcnt);
    for (int i = 0; i < rcnt; i++) printf("%d ", r[i]);
    return 0;
}