11518 Dominos 2

因為我演算法都習慣用Java寫，所以我多寫了Java的題解，再翻譯成C++，因此本篇有Java與C++的題解

題目敘述

給你n個骨牌，編號1~n 然後給你一個數字k，告訴你k次骨牌a倒下會導致骨牌b倒下 再給你一個數字p，總共要推倒p張骨牌，然後告訴你要推倒哪些骨牌(按順序推倒)(推倒的骨牌不會再立起來) 輸出有多少骨牌被推倒 題目要注意的地方: 骨牌被推倒後，就不會被別的骨牌推倒了，可以用陣列來記錄哪些骨牌被推倒 骨牌有可能一次讓超過一個骨牌倒下

輸入格式

先輸入一個整數S，接下來有S組測資 每一組測資的第一行有三個整數n,k,p n代表n張骨牌，k代表有多少骨牌會壓倒骨牌的關係，p代表要推倒多少骨牌 接下來有k行，每行兩個數字x,y，代表推倒骨牌x時，骨牌y會倒下 接下來有p行，每行一個數字，代表你要推倒的骨牌代號

關鍵知識點

圖遍歷

解題思路

訪問a會導致訪問b,c,d,...，訪問過的東西不會再度訪問 這種情況就跟圖一樣，可以把骨牌關係畫成一個有向圖，接下來就根據推倒的骨牌代號來BFS或DFS就可以了

import java.util.*;
public class CPE20240521_5 {
static int []check;
static int total;
static void DFS(Node n) {
	total++;
	check[n.data]=1;
	for(Node e:n.neig)
		if(check[e.data]==0)
			DFS(e);
}
public static void main(String[]args) {
	Scanner sc=new Scanner(System.in);
	int S=sc.nextInt();
	for(int IT=0;IT<S;IT++) {
		int n=sc.nextInt(),k=sc.nextInt(),p=sc.nextInt();
		check=new int[n];
		total=0;
		Node []arr=new Node[n];
		for(int i=0;i<n;i++)
			arr[i]=new Node(i);
		for(int i=0;i<k;i++) {
			int x=sc.nextInt()-1,y=sc.nextInt()-1;
			arr[x].neig.add(arr[y]);
		}
		for(int i=0;i<p;i++) {
			int j=sc.nextInt()-1;
			if(check[j]==0)
			DFS(arr[j]);
		}
		System.out.println(total);
	}
}
}
class Node {
	List<Node>neig=new ArrayList<>();
	int data;
	public Node(int data) {
		this.data=data;
	}
}

#include <iostream>
#include <vector>
using namespace std;

class node {
public:
    int data;
    vector<node*> neig;

    node(int I = 0) {
        data = I;
    }
};

static vector<int> check(10000);
static int total;

void DFS(node* n) {
    total++;
    check[n->data] = 1;
    for (node* e : n->neig) {
        if (!check[e->data])
            DFS(e);
    }
}

int main() {
    int S; cin >> S;
    while (S--) {
        int n, k, p; cin >> n >> k >> p;
        fill(check.begin(), check.end(), 0);
        total = 0;

        node arr[10000]; // 開大一點
        for (int i = 0; i < n; i++)
            arr[i] = node(i);

        while (k--) {
            int x, y; cin >> x >> y;
            x--; y--;
            arr[x].neig.push_back(&arr[y]);
        }

        while (p--) {
            int j; cin >> j; j--;
            if (!check[j])
                DFS(&arr[j]);
        }

        cout << total << endl;
    }
}