How Many Tables

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 60960    Accepted Submission(s): 30510


Problem Description
Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.

One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.

For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
 

 

Input
The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.
 

 

Output
For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.
 

 

Sample Input
2 5 3 1 2 2 3 4 5 5 1 2 5
 

 

Sample Output
2 4
 

 

Author
Ignatius.L
 

 

Source
杭电ACM省赛集训队选拔赛之热身赛
 

 

Recommend
Eddy
 


Statistic | Submit | Discuss | Note

 

题意

　　　　若干人聚餐吃饭准备桌子，认识的可以坐一桌，认识不需要互相认识，只要有A -> B, B -> C, 就有A -> C。

思路

　　　　认识的人并在一起，之后O(n)跑一遍，同一个并查集的人放在一个桌子上，如果桌子上有人则ans++

 

CODE

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 #include <cmath>
  6 #include <assert.h>
  7 #include <vector>
  8 
  9 #define dbg(x) cout << #x << "=" << x << endl
 10 
 11 using namespace std;
 12 typedef long long LL;
 13 const int maxn = 1007;
 14 
 15 int fa[maxn];
 16 int n,m,ans,cnt;
 17 int a[maxn];
 18 int tot[maxn];
 19 //vector <int> v;
 20 
 21 void init()
 22 {
 23     for(int i = 1; i <= n; i++) {
 24         fa[i] = i;
 25     }
 26 }
 27 
 28 int fid(int x)
 29 {
 30     int r = x;
 31     while(fa[r] != r) {
 32         r = fa[r];
 33     }
 34     int i,j;///路径压缩
 35     i = x;
 36     while(fa[i] != r) {
 37         j = fa[i];
 38         fa[i] =  r;
 39         i = j;
 40     }
 41     return r;
 42 }
 43 
 44 void join(int r1, int r2)///合并
 45 {
 46     int fidroot1 = fid(r1), fidroot2 = fid(r2);
 47     //int root = min(fidroot1, fidroot2);
 48     if(fidroot1 != fidroot2) {
 49         fa[fidroot2] = fidroot1;
 50         //fa[fidroot2] = root;
 51     }
 52 }
 53 
 54 template<class T>inline void read(T &res)
 55 {
 56     char c;T flag=1;
 57     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 58     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 59 }
 60 
 61 namespace _buff {
 62     const size_t BUFF = 1 << 19;
 63     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 64     char getc() {
 65         if (ib == ie) {
 66             ib = ibuf;
 67             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 68         }
 69         return ib == ie ? -1 : *ib++;
 70     }
 71 }
 72 
 73 int qread() {
 74     using namespace _buff;
 75     int ret = 0;
 76     bool pos = true;
 77     char c = getc();
 78     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 79         assert(~c);
 80     }
 81     if (c == '-') {
 82         pos = false;
 83         c = getc();
 84     }
 85     for (; c >= '0' && c <= '9'; c = getc()) {
 86         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 87     }
 88     return pos ? ret : -ret;
 89 }
 90 
 91 int main()
 92 {
 93     int t;
 94     scanf("%d",&t);
 95     while(t--) {
 96         memset(tot, 0, sizeof(tot));
 97         scanf("%d %d",&n, &m);
 98         init();
 99         for(int i = 1; i <= m; ++i) {
100             int a, b;
101             scanf("%d %d", &a, &b);
102             join(a,b);
103         }
104         for(int i = 1; i <= n; ++i) {
105             int x = fid(i);
106             tot[x]++;
107         }
108         int ans = 0;
109         for(int i = 1; i <= n; ++i) {
110             if(tot[i]) ans++;
111         }
112         cout << ans << endl;
113     }
114     return 0;
115 }
View Code