题解 | Cow Picnic-牛客假日团队赛3G题

输入描述:

这是一道对图进行深度优先遍历的一道很好的练习题。

从题面中，我们可以知道，这道题目是让我们对每只奶牛所在的点进行深度优先遍历，找到遍历的次数正好等于奶牛数的点，最后输出这样的点的数量。

我们使用一个数组表示点被遍历的次数，如果遍历到了点，那么就加。

注意：每次遍历之前都需要将判断点是否已经访问过的数组清空，并且每次在遍历下一个点的时候都需要判断点是否已经访问，因为每一个点在每次遍历中都是最多访问次。

另外，本题中的范围并不大，因此我们可以使用邻接矩阵来存图。

不难得出代码。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>//头文件准备

using namespace std;//使用标准名字空间

//以下为快速读入
inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar();}
    return f * x;
}

int n, m, k, ans, g[1003][1003], c[1003], s[1003], vis[1003];
//n,m,k的含义如题面,ans为最终答案,g数组为邻接矩阵,c数组存储牛的位置,s数组为每个点被遍历的次数,vis数组用来判断点是否已经被访问过

void dfs(int x)//进行图的深度优先遍历
{
    vis[x] = 1;//将现在访问的点标记为已遍历
    ++s[x];//将这个点遍历的次数+1
    for (int i = 1; i <= n; i++)//枚举节点编号
    {
        if (!vis[i] && g[x][i]) //如果当前节点没有被访问过并且与当前节点有边连接
            dfs(i);//就遍历i号节点
    }
}

int main()
{
    k = gi(), n = gi(), m = gi();//分别输入k,m,n(注意顺序)
    for (int i = 1; i <= k; i++) c[i] = gi();//输入每只奶牛的顺序
    for (int i = 1; i <= m; i++)
    {
        int u = gi(), v = gi(); //输入边两端的点的编号
        g[u][v] = 1;//连接两边(注意不是双向边,是单向边)
    }
    for (int i = 1; i <= k; i++)//对奶牛的位置进行枚举
    {
        dfs(c[i]);//从每一只奶牛的位置开始遍历
        memset(vis, 0, sizeof(vis));//记得每次遍历完都需要清空标记数组
    }
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == k) ++ans;//统计答案，如果当前节点被访问的次数恰好为奶牛的只数
    }
    printf("%d\n", ans);//输出最后答案
    return 0;//完美结束
}