PTA A_1013 Battle Over Cities

798236606

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

解：
DFS+邻接表

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

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

void DFS(int x)
{
    vis[x] = true;

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

int DFS_Traverse(void)
{
    int num = 0;

    for (int i = 1; i <= n; i++)
        if (!vis[i] && ++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[v1].push_back(v2);
        adj[v2].push_back(v1);
    }

    while (k--)
    {
        int check;

        scanf("%d", &check);

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

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