資訊之芽 2017 1415 排隊問題

sprout-lining-problem.cpp

#include<iostream>
//#include<cstdio>

struct node {
    int num;
    node* prev = nullptr;
    node* next = nullptr;
};

void printLine(node* head);
node* findTail(node* head);

int main() {
    int n, m;
    //scanf("%d%d", &n, &m);
    std::cin >> n >> m;
    node** nodes = new node*[n+1];
    node** lines = new node*[n+1];
    for(int i = 1; i <= n; i++) {
        nodes[i] = new node;
        nodes[i]->num = i;
        lines[i] = new node;
        lines[i]->next = nodes[i];
        nodes[i]->prev = lines[i];
    }
    for(int i = 0; i < m; i++) {
        int t, a, b;
        //scanf("%d%d%d", &t, &a, &b);
        std::cin >> t >> a >> b;
        if(t == 0) {
            nodes[a]->prev->next = nodes[a]->next;
            if(nodes[a]->next)
                nodes[a]->next->prev = nodes[a]->prev;

            node* oldNext = nodes[b]->next;

            nodes[b]->next = nodes[a];
            if(oldNext)
                oldNext->prev = nodes[a];

            nodes[a]->prev = nodes[b];
            nodes[a]->next = oldNext;
        } else if (t == 1 && lines[a]->next) {
            node* tail = findTail(lines[b]);
            tail->next = lines[a]->next;
            lines[a]->next->prev = tail;
            lines[a]->next = nullptr;
        }
    }
    for(int j = 1; j <= n; j++) {
        //printf("#%d:", j);
        std::cout << "#" << j << ":";
        printLine(lines[j]);
    }
}

node* findTail(node* head) {
    node* tail = head;
    while(tail->next)
        tail = tail->next;
    return tail;
}

void printLine(node* head) {
    node* n = head->next;
    while(n) {
        std::cout << " " << n->num;
        //printf(" %d", n->num);
        n = n->next;
    }
    printf("\n");
}