b298 - 老闆阿我要退貨

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個供應商關係圖，其中某些供應商被標記為有問題。給定一個供應商的列表，以及哪些供應商直接有問題，以及供應商之間的供應關係，要求判斷給定的供應商是否因為其上游供應商的問題而有問題。

解題思路

這題可以將供應商關係視為一個有向圖，其中邊表示供應關係。如果一個供應商直接或間接地依賴於有問題的供應商，那麼該供應商也被認為是有問題的。可以使用深度優先搜尋 (DFS) 來遍歷圖，從有問題的供應商開始，標記所有受影響的供應商。

程式碼中，chat 函數實現了 DFS。它檢查一個供應商是否已經被標記為有問題 (c[no].bad==1)。如果沒有，它會遞迴地檢查該供應商的所有上游供應商 (c[no].a)。如果任何一個上游供應商有問題，則將當前供應商標記為有問題，並返回 1。main 函數讀取輸入，建立圖，標記初始的有問題供應商，然後處理查詢，判斷每個查詢的供應商是否有問題。

複雜度分析

• 時間複雜度: O(N + M + Q)，其中 N 是廠商數量，M 是供應關係數量，Q 是查詢數量。DFS 的時間複雜度是 O(N + M)，因為它最多會遍歷所有節點和邊。處理查詢的時間複雜度是 O(Q)，因為對於每個查詢，我們需要調用 chat 函數，而 chat 函數的時間複雜度取決於圖的結構，最壞情況下是 O(N + M)。
• 空間複雜度: O(N + M)，其中 N 是廠商數量，M 是供應關係數量。c 陣列儲存了每個廠商的資訊，包括其上游供應商列表。在最壞情況下，c[i].a 可能包含所有其他廠商，因此空間複雜度是 O(N + M)。遞迴調用 chat 函數的深度可能達到 N，因此遞迴堆疊的空間複雜度也是 O(N)。

程式碼

#include <iostream>
#include <vector>
using namespace std;
struct shop{
	bool bad=0;
	vector <int> a;
};shop c[10001];
bool chat(int no){
	if(c[no].bad==1)return 1;
	for(auto i=c[no].a.begin();i!=c[no].a.end();++i){
		if(chat(*i)==1){
			c[no].bad=1;
			return 1;
		}
	}
	return 0;
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int n,m,l,q,x,y;
	while(cin >> n >> m >> l >> q){
		while(m--){
			cin >> x >> y;
			c[y].a.push_back(x);
		}
		while(l--){
			cin >> x;
			c[x].bad=1;
		}
		while(q--){
			cin >> x;
			(chat(x)==1)?cout << "TUIHUOOOOOO\n":cout << "YA~~\n";
		}
	}
}