[Jungol] 정올 2462 키 순서

출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1723&sca=40

Approach

문제 접근법 및 인접행렬로 구현된 코드는 [BOJ] 2458 키 순서 참고

[BOJ] 백준 2458 키 순서

 

연결리스트 이용한 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = 510;
struct Node {
    int data;
    Node* next;
    Node() {
        data = 0, next = NULL;
    }
    Node(int nd, Node* np) {
        data = nd, next = np;
    }
    ~Node() {
        delete next;
    }
};
 
int N, M, cnt[LM], ans;
int visit[LM], pivot;
Node* adj[LM];
 
void input() {
    scanf("%d %d", &N, &M);
    int i, u, v;
    for (i = 0; i < M; ++i) {
        scanf("%d %d", &u, &v);
        adj[u] = new Node(v, adj[u]);
    }
}
 
void DFS(int src, int now) {
    visit[now] = pivot;
 
    for (Node* p = adj[now]; p; p = p->next) {
        int child = p->data;
 
        if (visit[child] < pivot) {
            cnt[src]++; cnt[child]++;
            DFS(src, child);
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    for (int i = 1; i <= N; ++i) {
        pivot++;
        DFS(i, i);
    }
 
    for (int i = 1; i <= N; ++i) {
        ans += (cnt[i] == N - 1);
    }
 
    printf("%d\n", ans);
 
    // 메모리 해제
    for (int i = 1; i <= N; ++i) {
        delete adj[i];
    }
    return 0;
}

 

정적할당 이용한 방식

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int LM = 510;
struct Node {
       int data;
       Node* next;
       Node* alloc(int nd, Node* np) {
              data = nd, next = np;
              return this;
       }
}buf[LM * LM];
int bcnt;
int N, M, cnt[LM], ans;
int visit[LM], pivot;
Node* adj[LM];
void input() {
       scanf("%d %d", &N, &M);
       int i, s, e;
       for (i = 0; i < M; ++i) {
              scanf("%d %d", &s, &e);
              adj[s] = buf[bcnt++].alloc(e, adj[s]);
       }
}
void DFS(int src, int now) {
       // 현재 비교하고 있는 기준학생 번호를 방문 표시값으로 활용
       visit[now] = pivot;
       for (Node* p = adj[now]; p; p = p->next) {
              int child = p->data;
              // 아직 방문하지 않은 경우
              if (visit[child] < pivot) {
                     cnt[src]++; cnt[child]++;
                     DFS(src, child);
              }
       }
}
int main() {
       // freopen("input.txt", "r", stdin);
       input();
       for (int i = 1; i <= N; ++i) {
              pivot++;
              DFS(i, i);
       }
       for (int i = 1; i <= N; ++i) {
              ans += (cnt[i] == N - 1);
       }
       printf("%d\n", ans);
}