UVA11518 Dominos 2 题解

wwwidk1234 · 2023-07-30 17:23:11 · 题解

洛谷题目传送门

UVA 题目传送门

(也许)更好的阅读体验？

题目大意

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

题目分析

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

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

adj[u].push_back(v);

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

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);
    }
}

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

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;
}