主题：第40次编程比赛第1题题目
neverPE [专家分：1620] 发布于 2006-08-31 22:51:00
考虑到这次有2题，而且我明天中午也许不能上线。提前一点放出来，结束时间不变。
有n个学生. 每个学生都有自己的宗教信仰，可能相同，也可能不同。一个调查机构想弄清楚宗教信仰的总数。但是，直接询问可能会使人不快，于是，调查机构决定询问m对学生，问他们是否具有相同的宗教信仰。（如果相同，则他们会参加同一教会，彼此会认识）。要求计算最大可能的宗教数。
函数原型 int Religions(int n,int m,int* record);
n 人数 1<=n<=50000
m 抽查的学生对数，record中有2m个学生编号。 0<=m<=n*(n-1)/2 且 m<=500000
record[] 编号record[i*2]与record[i*2+1]的两个学生，他们之间有相同的信仰。0<=i<m,学生编号1～n
返回值：最大可能的宗教数。
内存限制：256M
时间限制：10S
样例：
n=10 m=9
record[]=
{1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10}
返回值：1
n=10 m=4
record[]=
{2 3
4 5
4 8
5 8}
返回值：7
一点提示：不要想太复杂了。
回复列表 （共29个回复）
沙发
jackin0627 [专家分：1270] 发布于 2006-08-31 21:53:00
int Religions(int n,int m,int* record)
{
int *f=new int[n+1];
int i,j,count=0,s=1;
memset(f,0,(n+1)*sizeof(int));
for(i=0;i<2*m;i+=2)
{
if( f[record[i]]==0 && f[record[i+1]]==0 )
{
f[record[i]]=s;
f[record[i+1]]=s++;
count++;
}
else if(f[record[i]]!=0 && f[record[i+1]]==0 )
{
f[record[i+1]]=f[record[i]];
count++;
}
else if(f[record[i]]==0 && f[record[i+1]]!=0 )
{
f[record[i]]=f[record[i+1]];
count++;
}
else if(f[record[i]] != f[record[i+1]])
{
for(j=0;j<n;j++)
{
int t=f[record[i+1]];
if(f[j]==t)
{
f[j]=f[record[i]];
}
}
count++;
}
}
return n-count;
}
板凳
天边蓝 [专家分：1810] 发布于 2006-08-31 22:08:00
int data[50000];
int Religions(int n,int m,int* record){
int count=0;
for(int i=0;i<n;i++)
data[i]=1;
for(int i=0;i<m;i++){
if(data[ record[2*i] ]==1&&data[ record[2*i+1] ]==1){
count++;
data[ record[2*i] ]=0;
data[ record[2*i+1] ]=0;
}
else{
data[ record[2*i] ]=0;
data[ record[2*i+1] ]=0;
}
}
for(i=0;i<n;i++)
count+=data[i];
return count;
}
3 楼
iAkiak [专家分：8460] 发布于 2006-08-31 22:40:00
改一下，不直接用ufset，原连接不需要保存，把结点尽量直接指向祖先结点减少以后查询的深度。
#include <cstdio>
#include <cassert>
#include <vector>
using namespace std;
struct UFSet
{
UFSet(int count) :
parent(count + 1, 0), island(count)
{
}
int island;
void Union(int a, int b)
{
int la, lb;
int sa = Find(a, la), sb = Find(b, lb);
if (sa == sb)
return;
if (la > lb)
{
parent[sb] = sa;
if (a != sa)
parent[a] = sa;
parent[b] = sa;
}
else
{
parent[sa] = sb;
if (b != sb)
parent[b] = sb;
parent[a] = sb;
}
island--;
}
int Find(int a, int &len)
{
assert(a > 0 && a < parent.size());
len = 0;
while(parent[a] > 0)
a = parent[a], len++;
return a;
}
vector<int> parent;
};
int Religions(int n,int m,int* record)
{
UFSet s(n);
int i;
for (i = 0; i < m; i++)
{
s.Union(record[i*2], record[i*2+1]);
}
return s.island;
}
4 楼
noairyu [专家分：0] 发布于 2006-09-01 07:22:00
走了， 大家编程去啦～～～～～
5 楼
liyanguestc [专家分：90] 发布于 2006-09-01 10:38:00
#include <iostream>
using namespace std;
int Religions(int n,int m,int* record);
int main()
{int n,m;
static int a[500000];
freopen("c:\\in.txt","r",stdin);
cin>>n>>m;
for(int i=0;i<2*m;i+=2)
cin>>a[i]>>a[i+1];
int num=Religions(n,m,a);
cout<<num<<endl;
return 0;}
int Religions(int n,int m,int* record)
{int count=0;
int b[50000];
for(int j=0;j<n;j++)
b[j]=1;
for(j=0;j<2*m;j+=2)
if(b[record[j]-1]&&b[record[j+1]-1])
{count++;
b[record[j]-1]=0;
b[record[j+1]-1]=0;
}
else
{b[record[j]-1]=0;
b[record[j+1]-1]=0;
}
for(j=0;j<n;j++)
count+=b[j];
return count;
}
6 楼
joekings [专家分：550] 发布于 2006-09-01 11:14:00
#include <stdlib.h>
#include <stdio.h>
int Religions(int n,int m,int* record);
int main()
{
int iRet;
int record[]={1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,1,10};
iRet=Religions(10,9,record);
printf("**%d**\n",iRet);
return 0;
}
int Religions(int n,int m,int* record)
{
int *ip;
int i,iNum,iCount=0;
ip=new int[n];
for(i=0;i<n;i++)
ip[i]=1;
for(i=0;i<m;i++)
{
iNum=(record[i*2]>record[i*2+1]?record[i*2]:record[i*2+1]);
ip[iNum-1]=0;
}
for(i=0;i<n;i++)
if(ip[i])
iCount++;
return iCount;
}
7 楼
liangbch [专家分：1270] 发布于 2006-09-01 11:37:00
#include "stdio.h"
#include "stdlib.h"
#include "memory.h"
int Religions(int n,int m,int* record)
{
int *p,*pEnd,*buff;
register int t0,t1;
int i,r,c=0;
buff=new int[n+1];
memset(buff,0,sizeof(int)*(n+1));
for (pEnd=record+m*2,p=record;p<pEnd;p+=2)
{
t0=p[0]; t1=p[1];
r= ( buff[t0] | buff[t1]);
if (r)
buff[t0]=buff[t1]=r;
else
buff[t0]=buff[t1]=++c;
}
for (i=1;i<=n;i++)
if (buff[i]==0)
c++;
delete[] buff;
return c;
}
8 楼
Cyre [专家分：0] 发布于 2006-09-01 11:41:00
#include<stdio.h>
int Religions(int n,int m,int* record)
{
int count,i,j,k;
count = n-m;
for(i=0;i<2*m;i+=2)
{
for(j=0;j<i-1;j++)
for(k=0;k<i;k++)
if((record[i]==record[j])&&(record[i+1]==record[k]))
count+=1;
}
return count;
}
void main(void)
{
int n=10,m=4;
int record[]={2,3,4,5,4,8,5,8};
int res;
res=Religions(n,m,record);
printf("%d",res);
}
9 楼
Cyre [专家分：0] 发布于 2006-09-01 11:49:00
不好意思 把测试部分的代码也一起发上来了......实在不好意思.....
10 楼
yelv [专家分：0] 发布于 2006-09-01 12:42:00
int Religions(int n, int m, int* record)
{
int i, j;
int count = 0;
int flag;
int countCheck = m;
if (n>=50000) return 0;
if (m<0 || m>n*(n-1)/2 || m>=500000) return 0;
for (i=1; i<=n; i++)
{
flag = 0;
for (j=0; j<2*m; j++)
{
if (i == record[j]) flag = 1;
}
if (flag == 0) count++;
}
printf("count = %d\n", count);
for (i=0; i<m-1; i++)
{
flag = 0;
for (j=2*(i+1); j<2*m; j++)
{
if (record[i*2] == record[j] || record[i*2+1] == record[j])
{
flag = 1;
printf("flag = %d, i= %d, j = %d\n", flag, i, j);
break;
}
}
if (flag == 1) countCheck--;
}
printf("countCheck = %d\n", countCheck);
count += countCheck;
return count;
}
我来回复
您所在位置：