题目链接

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;

}

巴特西

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

错误思路

WA代码

最新文章

热门文章

巴特西

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

错误思路

WA代码

最新文章

热门文章

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