A134859.午枫的传话游戏 题解

Latex 语言可能不是很好，请见谅。

题目大意：

有 $n$ 个数 $a_i$，$a_i$ 和 $a_j$ 可以联系当且仅当 $|a_i-a_j|=1$ 或他们可以按此联系方式通过若干”中间人“互相联系。

求能互相联系的同学集合的数量减 $1$。

发现一个能互相联系的同学集合一定排序后一定形如 $\{$若干个 $x$，若干个 $x+1$，若干个 $x+2$...... $\}$。

然后这个集合有多少个 $x$ 其实不重要，只需要知道这个集合里面有这个数就行了。

又看到 $a_i\le 2\times 10^5$，所以搞个标记数组标记一下。然后依次找每个 $a_i$ 有没有被标记过，没有的话就让计数 $+1$ 并进行搜索拓展。对于每个带拓展的 $x$，搜索 $x-1$ 和 $x+1$ 有没有被标记，没有就把他标记上，然后继续拓展。以此类推。答案即为计数减 $1$。

坑点解析：搜索刚开始的时候是不能标记 $a_i$ 被搜索过的，不然会在第二组测试数据这种被卡掉。

int a[200009];//输入的a[i]
bool vis[200009];//标记每个数有没有被搜过
bool had[200009];//标记这个数存不存在

void bfs(int x){
    queue<int> q;
    q.push(x);
    while(q.size()){
        int u = q.front();q.pop();
        if(had[u-1]&&!vis[u-1]){
            vis[u-1] = 1;
            q.push(u-1);
        }
        if(had[u+1]&&!vis[u+1]){
            vis[u+1] = 1;
            q.push(u+1);
        }
    }
}

        for(int i = 1;i<=n;++i){
            cin>>a[i];
            had[a[i]] = 1;
        }
        int cnt = 0;
        for(int i = 1;i<=n;++i){
            if(!vis[a[i]]&&had[a[i]]){
                cnt++;
                bfs(a[i]);
            }
        }