PAT 天梯赛 L3-003. 社交集群 【并查集】

题目链接

https://www.patest.cn/contests/gplt/L3-003

思路

并查集

用一个 cou[i] 来表示 第 i 门课程 的第一个 感兴趣的人

并的时候

判断 cou[i]

如果 cou[i] 存在 第一个 感兴趣的人 那么 将这两人 join 起来

如果 不存在 那么 这门课程 第一个感兴趣的人 就是这个人

然后 最后查找有几个 连通块

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

const double PI  = 3.14159265358979323846264338327;

const double E   = exp(1);

const double eps = 1e-6;

const int INF  = 0x3f3f3f3f;

const int maxn = 1e3 + 5;

const int MOD  = 1e9 + 7;

int pre[maxn], cou[maxn];

int find(int x)

{

    int r = x;

    while (pre[r] != r)

        r = pre[r];

    int j = x, i;

    while (j != r)

    {

        i = pre[j];

        pre[j] = r;

        j = i;

    }

    return r;

}

void join(int x, int y)

{

    int fx = find(x), fy = find(y);

    if (x != fy)

        pre[fx] = fy;

}

bool comp(int x, int y)

{

    return x > y;

}

int main()

{

    CLR(cou);

    int n, k, num;

    cin >> n;

    for (int i = 1; i <= n; i++)

        pre[i] = i;

    for (int i = 1; i <= n; i++)

    {

        scanf("%d:", &k);

        for (int j = 0; j < k; j++)

        {

            scanf("%d", &num);

            if (cou[num])

                join(i, cou[num]);

            else

                cou[num] = i;

        }

    }

    map <int, int> m;

    for (int i = 1; i <= n; i++)

        m[find(i)]++;

    vector <int> v;

    map <int, int>::iterator it;

    for (it = m.begin(); it != m.end(); it++)

        v.push_back(it -> second);

    sort (v.begin(), v.end(), comp);

    int len = v.size();

    cout << len << endl;

    for (int i = 0; i < len; i++)

    {

        if (i)

            printf(" ");

        printf("%d", v[i]);

    }

    cout << endl;

}

错误思路

用一个结构体 来保存 社交集群

第一个人 自然就是 第一个社交集群

结构体中 保存 人数 以及 里面所有人感兴趣的课程

然后 从第二个人开始 就开始 在已经有的社交集群里面查找 自己的感兴趣的课程 是否 已经有的社交集群中已经存在 如果有 那么 就加入

如果没有 自己就新建一个 社交集群

但是这样有一个问题

就是 后面查找的时候

如果一个人 同时 与两个 甚至多个 社交集群 都有同时感兴趣的课程

是要将这两个甚至多个 社交集群 并起来的。。

少了 这一步 操作 所以 代码 只能拿 20分

WA代码

#include <cstdio>       //错误思路

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

const double PI  = 3.14159265358979323846264338327;

const double E   = exp(1);

const double eps = 1e-6;

const int INF  = 0x3f3f3f3f;

const int maxn = 1e3 + 5;

const int MOD  = 1e9 + 7;

struct Node

{

    int id;

    int tot;

    map <int, int> m;

}temp;

bool comp(Node x, Node y)

{

    return x.tot > y.tot;

}

int main()

{

    vector <Node> v;

    map <int, int> vis;

    int n, k, num;

    cin >> n;

    for (int i = 1; i <= n; i++)

    {

        scanf("%d:", &k);

        temp.id = v.size() + 1;

        temp.tot = 1;

        temp.m.clear();

        int flag = 0, opt;

        for (int j = 0; j < k; j++)

        {

            scanf("%d", &num);

            if (vis[num])

            {

                flag = 1;

                opt  = vis[num];

            }

            temp.m[num] = 1;

        }

        if (flag)

            v[opt - 1].tot++;

        else

        {

            v.push_back(temp);

            opt = temp.id;

        }

        opt--;

        map <int, int>::iterator it;

        for (it = temp.m.begin(); it != temp.m.end(); it++)

        {

            v[opt].m[it -> first] = 1;

            vis[it -> first] = v[opt].id;

        }

    }

    sort (v.begin(), v.end(), comp);

    cout << v.size() << endl;

    vector <Node>::iterator iter;

    for (iter = v.begin(); iter != v.end(); iter++)

    {

        if (iter != v.begin())

            printf(" ");

        printf("%d", (*iter).tot);

    }

    cout << endl;

}