[BOJ] 백준 17616 등수 찾기

출처: www.acmicpc.net/problem/17616

Approach

[Jungol] 2462 키 순서 문제와 유사하다.

[Jungol] 정올 2462 키 순서

 

전체 학생 수 N ≤ 100,000이며, 질문 횟수 M ≤ 500,000이기 때문에 

인접행렬로는 학생들의 등수 관계를 표현할 수 없다. → 인접리스트로 구현

 

X 번 학생의 등수 범위를 알기 위해서는 자기 위와 아래에 몇명이 있는지 알 수 있어야 합니다.

그렇기에 보다 작은 학생들에 대한 인접리스트(dwAdj)와 보다 큰 학생들에 대한 인접리스트(upAdj) 2개를 이용합니다.

▶ 2개의 인접리스트(upAdj, dwAdj)를 순차적으로 탐색

(Memory Pool을 이용하려면 질문 횟수 M의 2배만큼 공간 준비)

---

동적 할당

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int LM = 100010;
struct Node {
    int child;
    Node* next;
    Node(){
        child = 0, next = NULL;
    }
    Node(int nc, Node* np){
        child = nc, next = np;
    }
    ~Node(){
        delete next;
    }
};
int N, M, X, upCnt, dwCnt;
Node * upAdj[LM], *dwAdj[LM];
bool visit[LM];
 
void input() {
    int i, u, v;
    scanf("%d %d %d", &N, &M, &X);
    for (i = 0; i < M; ++i) {
        scanf("%d %d", &u, &v);
        dwAdj[u] = new Node(v, dwAdj[u]);
        upAdj[v] = new Node(u, upAdj[v]);
    }
}
void DFS(int now, int& cnt, Node** adj) {
    if (visit[now]) return;
    cnt++;
    visit[now] = 1;
    for (Node* p = adj[now]; p; p = p->next) {
        DFS(p->child, cnt, adj);
    }
}
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    DFS(X, upCnt, upAdj);
    
    visit[X] = 0;
    DFS(X, dwCnt, dwAdj);
    printf("%d %d", upCnt, N - dwCnt + 1);
 
    for(int i=1; i<=N; ++i){
        delete upAdj[i];
        delete dwAdj[i];
 
    }
}

 

정적 할당

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int LM = 100010; // 100,010
int N, M, X, upCnt, dwCnt;
struct Node {
    int child;
    Node* next;
    Node* alloc(int nc, Node* np) {
        child = nc, next = np;
        return this;
    }
}buf[LM * 10]; // 최대 M의 2배 = 500,000 x 2
int bcnt;
Node * upAdj[LM], *dwAdj[LM];
bool visit[LM];
void input() {
    int i, u, v;
    scanf("%d %d %d", &N, &M, &X);
    for (i = 0; i < M; ++i) {
        scanf("%d %d", &u, &v);
        dwAdj[u] = buf[bcnt++].alloc(v, dwAdj[u]);
        upAdj[v] = buf[bcnt++].alloc(u, upAdj[v]);
    }
}
void DFS(int now, int& cnt, Node** adj) {
    if (visit[now]) return;
    cnt++;
    visit[now] = 1;
    for (Node* p = adj[now]; p; p = p->next) {
        DFS(p->child, cnt, adj);
    }
}
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    DFS(X, upCnt, upAdj);
 
    visit[X] = 0;
    DFS(X, dwCnt, dwAdj);
    printf("%d %d", upCnt, N - dwCnt + 1);
}