题解：P11545 [Code+#5] 监控中心

HZEason_Ai · 2025-03-29 21:20:48 · 题解

题目大意

给定一个 n 个点 m 条边的无向图，对于 q 组测试数据输出不能与所有点联通的点的个数。

坑点

• 对于城市 a_i 和 b_i 不一定只有一个情报中心。

• 在遍历图的过程中可能会因递归堆栈过多爆空间。

• 有自己指向自己的边，需要筛掉（或者在计算答案的时候直接过滤掉）。

吐槽：阅读理解题还给特解样例[○･｀Д´･ ○]

分析

因为样例太特殊，所以自己造了组样例，设 u 表示发出信号的点、v 为被报告的点，下面来分析两种操作。

• 若 u 是 v 的儿子（因为 u,v 只能是 a_i 或 b_i，所以不需要并查集来找父亲，但需要考虑上文提到的 a_i=b_i 的情况），则只有 u 的子树（包括自己）符合条件。

• 若 v 是 u 的儿子，则 v 的子树都不符合条件。

看一组样例：

7 6
1 2
1 3
2 4
2 5
3 6
3 7
3
3 -1 6 5
2 -1 -2
2 1 2

对于 3 -1 6 5 这组数据，答案应为 4+1+1=6。

对于 2 -1 -2 这组数据，显然只有 1 不行，所以答案为 1。

对于 2 1 2 这组数据，显然只有 1 行，所以答案为 6。

再看不懂就直接看代码吧：

#include<bits/stdc++.h>
//#define int long long
#define endl "\n"
#define er puts("")
#define sc putchar(' ')
#define AzureLine return 0
using namespace std;
const int N=25e5+5;
int a[N],b[N],sz[N],fa[N];
vector<int>e[N];
void dfs(int x)
{
    sz[x]=1;//子树算上自己
    for(int i=0;i<e[x].size();i++)
    {
        int y=e[x][i];
        if(fa[y]) continue; //双向边，记得continue
        fa[y]=x;dfs(y);
        sz[x]+=sz[y];
    }
}
int read()
{
    int x=0,a=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-') a=-1;
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-'0';
    return x*a;
}
void write(int x)
{
    if(x<0) x*=-1,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return;
}
signed main()
{
    int n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        a[i]=read(),b[i]=read();
        e[a[i]].push_back(b[i]);
        e[b[i]].push_back(a[i]);
    }
    fa[1]=-1;dfs(1);
//  for(int i=1;i<=n;i++) write(sz[i]),sc;
    int q=read();
    while(q--)
    {
        int c=read(),ans=0;//多测清空
        for(int i=1;i<=c;i++)
        {
            int x=read(),u,v;
            if(x>0) u=a[x],v=b[x];
            else u=b[-x],v=a[-x];
            if(u==fa[v]) ans+=sz[v];
            if(v==fa[u]) ans-=sz[u];
        }
        write(ans>=0?ans:ans+n),er;//如果ans为负，那显然是应为求的是合适的点，所以加n
    }
    return 0;
}