k849 - P3.骨牌 (Domino)

🔗 前往 ZeroJudge 原題

題目描述

題目給定一系列的骨牌，每塊骨牌由兩個數字表示，代表骨牌的正反兩面。題目要求找出所有從未被匹配的骨牌的開頭序列，並將其輸出。骨牌的匹配規則是，如果一塊骨牌的尾部數字等於另一塊骨牌的頭部數字，則可以將這兩塊骨牌連接起來。

解題思路

這題可以將骨牌看作一個鏈表，每個骨牌的頭部數字是當前節點的值，尾部數字是指向下一個節點的索引。題目要求找到所有鏈表的起始節點，也就是沒有前驅節點的節點。程式碼首先讀取骨牌的頭尾數字，並建立一個 nxt 陣列和 pre 陣列，分別儲存每個骨牌的下一個節點和前一個節點。然後，程式碼遍歷 nxt 陣列，找到所有沒有前驅節點的節點，並從這些節點開始，按照鏈表的方式輸出所有節點的值。

複雜度分析

• 時間複雜度: O(N)，其中 N 是骨牌的數量。程式碼需要遍歷所有骨牌來建立鏈表，然後遍歷鏈表來輸出結果。
• 空間複雜度: O(N)，其中 N 是骨牌的數量。程式碼需要使用 nxt 和 pre 陣列來儲存鏈表的資訊。

程式碼

#include <iostream>
using namespace std;
int x,y,nxt[1001],pre[1001];
int main(){
	cin >> x;
	while(cin >> x >> y){
		nxt[x]=y;
		pre[y]=x;
	}
	for(int i=0;i<1001;++i){
		if(nxt[i]&&!pre[i]){
			int tmp=i;
			while(tmp!=-1){
				cout << tmp << " ";
				tmp=nxt[tmp];
			}
		}
	}
	return 0;
}