PAT甲級1107

1107. Social Clusters (30)

時間限制

1000 ms

記憶體限制

65536 kB

代碼長度限制

16000 B

判題程式

Standard

作者

CHEN, Yue

When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A "social cluster" is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (<=1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:

Ki: hi[1] hi[2] ... hi[Ki]

where Ki (>0) is the number of hobbies, and hi[j] is the index of the j-th hobby, which is an integer in [1, 1000].

Output Specification:

For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

8

3: 2 7 10

1: 4

2: 5 3

1: 4

1: 3

1: 4

4: 6 8 1 5

1: 4

Sample Output:

3

4 3 1

/*
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
const int maxn = 1000;
bool hashtable[maxn] = { false };
set<int> person[maxn+1];
vector<int> clusters;
bool isCommon(set<int> s1, set<int> s2)
{
  set<int>::iterator it;
  bool flag = false;
  for (it = s2.begin(); it != s2.end(); it++)
  {
    if (s1.find(*(it)) != s1.end())
    {
      flag = true;
      break;
    }
  }
  return flag;
}
void unionset(set<int> &s1, set<int> s2)
{
  for (set<int>::iterator it = s2.begin(); it != s2.end(); it++)
  {
    s1.insert(*(it));
  }
}
int cmp(set<int> s1, set<int> s2)
{
  return s1.size() > s2.size();
}
int main()
{
  int N;
  scanf("%d", &N);
  int k, h;
  for (int i = 1; i <= N; i++)
  {
    scanf("%d", &k);
    getchar();
    for (int j = 0; j < k; j++)
    {
      scanf("%d", &h);
      person[i].insert(h);
    }
  }
  sort(person+1, person + 1+N, cmp);
  vector<int> v;
  int sum = 0;
  for (int i = 1; i <= N; i++)
  {
    int count = 1;
    if (!hashtable[i])
    {
      for (int j = i + 1; j <= N; j++)
      {
        if (isCommon(person[i], person[j]) && !hashtable[j])
        {
          count++;
          unionset(person[i], person[j]);
          hashtable[j] = true;
        }
      }
      for (int j = i + 1; j <= N; j++)
      {
        if (isCommon(person[i], person[j]) && !hashtable[j])
        {
          count++;
          unionset(person[i], person[j]);
          hashtable[j] = true;
        }
      }
      for (int j = i + 1; j <= N; j++)
      {
        if (isCommon(person[i], person[j]) && !hashtable[j])
        {
          count++;
          unionset(person[i], person[j]);
          hashtable[j] = true;
        }
      }
      for (int j = i + 1; j <= N; j++)
      {
        if (isCommon(person[i], person[j]) && !hashtable[j])
        {
          count++;
          unionset(person[i], person[j]);
          hashtable[j] = true;
        }
      }
      sum += count;
      if (sum <= N)
      {
      v.push_back(count);
      hashtable[i] = true;
      }
    }
  }
  printf("%d\n", v.size());
  sort(v.begin(), v.end());
  for (int i = v.size()-1; i>=0; i--)
  {
    printf("%d", v[i]);
    if (i)
      printf(" ");
    else
      printf("\n");
  }
  return 0;

}
本人的暴力解法，也可以全過，中間為什麼要弄4個for循環，因為在順序周遊時當set加入其它元素後，也會使得之前掃描過的滿足共同興趣
是以需要再掃描一遍
3
5
3 5
這就是活生生的例子，3跟5不是共同興趣，而3跟3 5有共同興趣，合并後使得5也可以并入其中
而有些情況掃描兩遍還不夠
*/
//下面是并查集解法
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1010;
int father[N];//存放父親結點
int isRoot[N] = { 0 };//記錄每個結點是否作為某個集合的根結點
int course[N] = { 0 };
/*int findFather(int x)//查找x所在集合的根結點
{
  int a = x;
  while (x != father[x])
  {
    x = father[x];
  }
  //路徑壓縮
  while (a != father[a])
  {
    int z = a;
    a = father[a];
    father[z] = x;
  }
  return x;
}*/
/*
遞歸版本，路徑壓縮：*/
int findFather(int x)
{
  if (x == father[x])return x;
  else
  {
    int F = findFather(father[x]);
    father[x] = F;
    return F;
  }
}
/**/
void Union(int a, int b)//合并a和b所在的集合
{
  int faA = findFather(a);
  int faB = findFather(b);
  if (faA != faB)
    father[faA] = faB;
}
void init(int n)//初始化father[i]為i，且flag[i]為false
{
  for (int i = 1; i <= n; i++)
  {
    father[i] = i;
    isRoot[i] = false;
  }
}
bool cmp(int a, int b)//isRoot數組從大到小排序
{
  return a > b;
}
int main()
{
  int n, k, h;
  scanf("%d", &n);//人數
  init(n);//要記得初始化
  for (int i = 1; i <= n; i++)//對每個人
  {
    scanf("%d:",&k);//活動個數
    for (int j = 0; j < k; j++)//對每個活動
    {
      scanf("%d", &h);//輸入i号人喜歡的活動h
      if (course[h] == 0)//如果活動h第一次有人喜歡
      {
        course[h] = i;//令i喜歡活動h
      }
      Union(i, findFather(course[h]));//合并
    }
    
  }
  for (int i = 1; i <= n; i++)
  {
    isRoot[findFather(i)]++;//i的根結點是findFather(i),人數加1
  }
  int ans = 0;//記錄集合數目
  for (int i = 1; i <= n; i++)
  {
    if (isRoot[i] != 0)
    {
      ans++;//隻統計isRoot[i]不為0的
    }
  }
  printf("%d\n", ans);//輸出集合個數
  sort(isRoot + 1, isRoot + 1 + n, cmp);//從大到小排序
  for (int i = 1; i <= ans; i++)//依次輸出每個集合内的個數
  {
    printf("%d", isRoot[i]);
    if (i < ans)printf(" ");
  }
  return 0;
}