UVA11518 Dominos 2 题解

题目大意

一组多米诺骨牌，将用手推倒若干个，被推倒的多米诺骨牌可让后面的多米诺骨牌倒下，问有几个多米诺骨牌被推倒。

题目分析

可将多米诺骨牌视为一个有向图，要模拟推倒的过程，可用深度优先遍历方法。

考虑使用邻接表储存图，首先读入要存的边 $u,v$ ，随后将边存入 vector 里：

1	adj[u].push_back(v);

随后读入起始点 $z$ ，以 $z$ 为起点，对图进行 DFS 操作。

1 2	cin >> z; dfs(z);

然后将 DFS 函数补充完整。

void dfs(int u)
{
	vis[u] = true;
	int siz = adj[u].size();
	for(int i = 0; i < siz; ++i)
	{
		int now_point = adj[u][i];
		if(!vis[now_point]) dfs(now_point);
	}
}

最后，统计被访问过的点的个数，并输出。

1 2	for(int i = 1; i <= n; i++) ans += vis[i]; cout << ans << endl;

注意：因为有多组数据，所以应在每组数据处理之前清空邻接表以及标记数组。

完整代码

#include<bits/stdc++.h>
using namespace std;
const short MAXN = 10010;
vector<int> adj[MAXN];
bool vis[MAXN];
int n, m, l;
void dfs(int u)
{
	vis[u] = true;
	int siz = adj[u].size();
	for(int i = 0; i < siz; ++i)
	{
		int now_point = adj[u][i];
		if(!vis[now_point]) dfs(now_point);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int u, v;
	int T;
	cin >> T;
	while(T--)
	{
		for(int i = 1; i <= n; i++) adj[i].clear();
		memset(vis, 0, sizeof vis);

		cin >> n >> m >> l;
		while(m--)
		{
			cin >> u >> v;
			adj[u].push_back(v);
		}
		int z;
		while(l--)
		{
			cin >> z;
			dfs(z);
		}
		int ans = 0;
		for(int i = 1; i <= n; i++) ans += vis[i];
		cout << ans << endl;
	}
	return 0;
}

题外话

这是本蒟蒻第一篇图论题题解。

本蒟蒻做此题时吃了 $9$ 发 WA：

在第十次终于 AC 了：https://www.luogu.com.cn/record/118131412