줄 세우기 아메리칸 조식

1. 위상 정렬 2. 링크드 리스트 3. 큐로 풀이 가능함 4. 디그리 0인가? 5. 아하 그냥 이렇게 풀이 한 것 이구나

#include <stdio.h> struct NODE { int n; NODE* next; }; const int MAXN = 50000, MAXM = 150000; NODE* list[MAXN + 1]; // 각 시작점을 저장함 NODE nPool[MAXM]; // 전체 간선을 저장함 int CHK[MAXN + 1]; // 들어오는 것의 갯수를 저장함 int QUEUE[MAXN]; int wp, rp; int tc, T, N, M, a, b, s; void process(void) { wp = 0, rp = 0; for (int i = 1; i <= N; ++i) { if (CHK[i] == 0) QUEUE[wp++] = i; // 시작점을 찾기 } while (rp < wp) // 들어오는 것 없으니, 시작하는 것들 { s = QUEUE[rp++]; for (NODE* n = list[s]; n != NULL; n = n->next) { if (--CHK[n->n] == 0) QUEUE[wp++] = n->n; } } } int main(void) { freopen("input.txt", "r", stdin); for (tc = scanf("%d", &T); tc <= T; ++tc) { scanf("%d%d", &N, &M); for (int i = 0; i < M; ++i) { scanf("%d%d", &a, &b); NODE* n = &nPool[i]; n->n = b, n->next = list[a], list[a] = n; ++CHK[b]; } printf("#%d", tc); process(); for (int i = 0; i < wp; ++i) printf(" %d", QUEUE[i]); // 저장된 것 앞으로 나오도록 for (int i = 1; i <= N; ++i) CHK[i] = 0, list[i] = NULL; // 초기화 puts(""); } return 0; }