(백준 알고리즘 문제풀이) 2252번 줄세우기

#include <string>
#include <cstdio>
#include <queue>

using namespace std;

int* in;
queue<int> q;


struct Node { 
    int data;
    Node* next, * prev; 
    Node() {
        next = prev = NULL;
        data = 0;
    }
    Node(int i, Node* ptr)//ptr 뒤에 추가
    {
        data = i;
        prev = ptr;
        next = ptr->next;
        next->prev = prev->next = this; 
    }
    void selvDelete() {
        prev->next = next;
        next->prev = prev;
        delete this;
    }
};

struct LinkedList {
    Node *head;
    Node *tail;
    int count;
    LinkedList() { //생성자
        count = 0;
        head = new Node(); //더미를 선언해서 가지고 있게한다.
        tail = new Node(); //더미를 선언해서 가지고 있게한다.
        head->next = tail; //서로연결한다.
        tail->prev = head;
    }
    void endInsert(int i) { //tail 앞에 추가한다.
        new Node(i, tail->prev);
    }
    void eraseQueue() {
        Node* tmp = head;
        while (tmp->next != NULL) {
            in[tmp->data] --;
            if(in[tmp->data] == 0) q.push(tmp->data);
            tmp = tmp->next;
        }
    }
};


int main(){
    int N, M, v1, v2;
    scanf("%d %d", &N, &M);
    LinkedList **list = new LinkedList*[N+1];
    for(int i = 0; i < N + 1; i++)list[i] = new LinkedList();
    in = new int[N+1];
    for(int i = 0; i < N + 1; i++)in[i] = 0;
    for(int i = 0 ; i < M; i++){
        scanf("%d %d", &v1, &v2);
        list[v1]->endInsert(v2);
        in[v2] ++;
    }
    for(int i = 1; i <N+1; i++){
        if(in[i] == 0) q.push(i);
    }

    while(!q.empty()){
        int temp = q.front();
        printf("%d ", temp);
        q.pop();
        list[temp]->eraseQueue();
    }
}

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int* in;
queue<int> q;

int main(){
    int N, M, v1, v2;
    scanf("%d %d", &N, &M);
    vector<vector<int> > v;
    for(int i = 0; i < N + 1; i++)v.push_back(vector<int>());
    in = new int[N+1];
    for(int i = 0; i < N + 1; i++)in[i] = 0;
    for(int i = 0 ; i < M; i++){
        scanf("%d %d", &v1, &v2);
        v[v1].push_back(v2);
        in[v2] ++;
    }
    for(int i = 1; i <N+1; i++){
        if(in[i] == 0) q.push(i);
    }

    while(!q.empty()){
        int temp = q.front();
        printf("%d ", temp);
        q.pop();
        for(int i = 0; i < v[temp].size(); i++){
            if(--in[v[temp][i]] == 0)q.push(v[temp][i]);
        }
    }    
}