游客 注册 | 登录
中文 | En

1655 - How Many Tables

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

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.

题目输入

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.

题目输出

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

输入/输出样例

输入格式

2
6 4
1 2
2 3
3 4
1 4

8 10
1 2
2 3
5 6
7 5
4 6
3 6
6 7
2 5
2 4
4 3

输出格式

3
2

C语言解答

#include <stdio.h>
int i,j,n,m,a[1001],b[1001],c[1001];
void make_set()
{
	scanf("%d%d",&n,&m);
        for(i=1;i<=m;i++)
                scanf("%d%d",&a[i],&b[i]);
        for(i=1;i<=n;i++)
                c[i]=i;
}
void count()
{
	j=1;
    while(j==1)
    {
		j=0;
        for(i=1;i<=m;i++)
        {
			if(c[a[i]]<c[b[i]])
            {
				j=1;
				c[b[i]]=c[a[i]];
            }
            if(c[a[i]]>c[b[i]])
            {
				j=1;
				c[a[i]]=c[b[i]];
            }
		}
	}
}
void print()
{
	j=0;
    for(i=1;i<=n;i++)
	{
		if(c[i]==i)
			j++;
	}
    printf("%d\n",j);
}
int main()
{
        int t;
        scanf("%d",&t);
        while(t--)
        {
			make_set();
			count();
			print();
        }
        return 0;
}

C++解答

#include <stdio.h>
int run()
{
	int n,m,a[1111],b[1111],c[1111],i,j,k;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d%d",&a[i],&b[i]);
	for(i=1;i<=n;i++)
		c[i]=i;
	k=1;
	while(k==1)
	{
		k=0;
		for(i=1;i<=m;i++)
		{
			if(c[a[i]]<c[b[i]])
			{
				k=1;
				c[b[i]]=c[a[i]];
			}
			if(c[a[i]]>c[b[i]])
			{
				k=1;
				c[a[i]]=c[b[i]];
			}
		}
	}
	j=0;
	for(i=1;i<=n;i++)
		if(c[i]==i)
			j++;
	printf("%d\n",j);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t!=0)
	{
		t--;
		run();
	}
	return 0;
}

Java解答

import java.io.*;
import java.util.*;

public class Main{
 static boolean b[]=new boolean[1005];
  static int f[]=new int[1005],r[]=new int[1005];
  static int getfather(int n){
   return f[n]=f[n]==n?n:getfather(f[n]); 
  }
  static void Union(int fa,int fb){
    if(r[fa]>=r[fb]){
     f[fb]=f[fa];r[fa]+=r[fb];
    }else{
     f[fa]=f[fb];r[fb]+=r[fa];
    }return;
  }
  public static void main(String args[]){
   Scanner jin=new Scanner(System.in);
    while(true){
     int T=jin.nextInt();
      while(T-->0){
       int N=jin.nextInt(),M=jin.nextInt();
        for(int i=1;i<=N;i++){
         r[i]=1;f[i]=i;b[i]=false; 
        }
        for(int i=0;i<M;i++){
         int A=jin.nextInt(),B=jin.nextInt();
          int fa=getfather(A),fb=getfather(B);
          if(fa!=fb)Union(fa,fb);
        }
        int cnt=0;
        for(int i=1;i<=N;i++)
          if(!b[getfather(i)]){
         b[getfather(i)]=true;
          cnt++;
        }
        System.out.println(cnt);
      }
    }
  }
}

Python解答

def space_input():
    s=raw_input().split()
    for i in range(len(s)):
        s[i]=eval(s[i])
    return tuple(s)
def main():
    try:
        n,p=space_input()
    except:
        n,p=space_input()
    friends=[{i} for i in range(1,n+1)]
    for i in range(p):
        a,b=space_input()
        contact={}
        for number in (a,b):
            for j in range(n):
                if number in friends[j]:
                    contact[number]=j
        if contact[a]<contact[b]:
            friends[contact[a]]=friends[contact[a]]|friends.pop(contact[b])
            n-=1
        elif contact[b]<contact[a]:
            friends[contact[b]]=friends[contact[b]]|friends.pop(contact[a])
            n-=1
    print len(friends)
t=input()
for i in range(t):
    main()
请先登陆