论坛 › C\C++交流 › PTA A_1013 Battle Over Cities

798236606 发表于 2020-2-16 17:20:51

PTA A_1013 Battle Over Cities

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805500414115840

解：
DFS+邻接表
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int n, m, k;
vector<int> adj;
bool vis;

void DFS(int x)
{
    vis = true;

    for (int i = 0; i < adj.size(); i++)
      if (!vis]) DFS(adj);
}

int DFS_Traverse(void)
{
    int num = 0;

    for (int i = 1; i <= n; i++)
      if (!vis && ++num) DFS(i);

    return num;
}

int main(void)
{
    scanf("%d %d %d", &n, &m, &k);

    while (m--)
    {
      int v1, v2;

      scanf("%d %d", &v1, &v2);

      adj.push_back(v2);
      adj.push_back(v1);
    }

    while (k--)
    {
      int check;

      scanf("%d", &check);

      fill(vis, vis + n + 1, false);
      vis = true;

       printf("%d\n", DFS_Traverse() - 1);
    }

    return 0;
}

查看完整版本: PTA A_1013 Battle Over Cities