J - Welcome Party ZOJ - 4109 【 并查集 + 优先队列 + BFS 】

J - Welcome Party

ZOJ - 4109 

&：这个就是看着题解搞得了，当时想到了优先队列和 BFS ，没有搞把所有的连起来，但是也没有尝试，当时在做字符串那个题，反正各种原因了。言归正传，题目的意思是，给你 n 个人，n 个人有 m 对关系，对于一个人，如果他上场了，发现没有他认识的人，会产生一个值，也就是 ans ，否则不会产生，问安排上场顺序让 ans 最小，且让上场序列的字典序最小。 &：题解：将 n 个人的 m 对关系来用并查集连起来，合并的时候只往小了合并，让小的先上场，这样合并完，跑一边 fa [ i ] 数组，就可以知道有几个连通块，ans 就是连通块的个数，把所有连通块的第一个节点都放到 0 里面，对 0 节点开始进行遍历，然后 BFS 时用优先队列优化。

代码语言：javascript复制

#include <bits/stdc  .h>
#define rep(i,a,b) for(int i = (a); i < (b); i   )
#define MM(x) memset(x,0,sizeof(x))
#define pb push_back
#define ll long long
using namespace std;
const int maxn = 2e6 5;
int fa[maxn];
bool vis[maxn];
int ans[maxn];
int t,n,m;
vector<int>ve[maxn];
int fin(int x){
    return fa[x] == x ? x : fa[x] = fin(fa[x]);
}
void mer(int a, int b)
{
    int u = fin(a);
    int v = fin(b);
    if(u < v) fa[v] = u;
    else fa[u] = v;
}
int bfs(int x)
{
    int num = 0;
    rep(i,0,n 1)vis[i] = false;
    priority_queue<int, vector<int>, greater<int> >pq;
    pq.push(x);
    while(!pq.empty())
    {
        int now = pq.top();
        pq.pop();
        if(vis[now] == 1)continue;
        vis[now] = 1;
        ans[num  ] = now;
        int sz = ve[now].size();
        rep(i,0,sz){
            int v = ve[now][i];
            if(vis[v])continue;
            else pq.push(v);
        }
    }
    return num;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n,&m);
        int u,v;
        rep(i,0,n 1)fa[i] = i,ve[i].clear();
        rep(i,0,m){
            scanf("%d %d", &u, &v);
            ve[u].pb(v); ve[v].pb(u);
            mer(u,v);
        }
        int sum = 0;
        rep(i,1,n 1){
            if(fa[i] == i){
                ve[0].pb(i);
                sum   ;
            }
        }
        int tot = 0;
        tot = bfs(0);
        printf("%dn",sum);
        rep(i,1,tot){
            if(i == 1)printf("%d",ans[i]);
            else printf(" %d",ans[i]);
        }
        printf("n");
    }
    return 0;
}

队列

0 人点赞