#define nStudentMax 50000
int Religions(int n,int m,int* record)
{
    int Group[nStudentMax+1];
    int ret = 0;
    int* record_end = record+m*2;
    for(int i=1; i<=n; ++i)
        Group[i] = i;
    while( record < record_end )
    {
        int a = *record++;
        int b = *record++;
        if( a < b )
            Group[b] = a;
        else
            Group[a] = b;
    }
    for(int i=1; i<=n; ++i)
    {
        if( Group[i] == i )
            ++ret;
    }
    return ret;
}

//---------------------------------------------------
// 测试用的代码
#include <cstdio>
int main()
{
    int a[] = {1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,1,10};
    int b[] = {2,3,4,5,4,8,5,8};
    int c[] = {1,2,3,4,2,3};
    printf("%d\n", Religions(10, 9, a)); // answer = 1
    printf("%d\n", Religions(10, 4, b)); // answer = 7
    printf("%d\n", Religions( 4, 3, c)); // answer = 1
    return 0;
}

\*昨天就弄好了，今天弄出来,第二次参加，望指导*\
\*思路是：用总数n减去所有的对数m(m代表的意思是相同信仰的人对数）*\
int Religions(int n,int m,int* record)
{ 
  int i, j;
  int count;
  int sum;
  sum = n - m;
\*当然还有这样的情况，就是说在数组中，1、3、5....位置上相同的情况，如果他们相同那就有可能是三个人的信仰，或者4个人，或者更多人的信仰相同，所有我再减去这些信仰相同的人，但是如果有3个相同的话，我仅仅是减去一个，因为他们本来在0、2、4..........中已经被减去了，就是我开始说的m对*\
  for(j = 1; j < = n; j++)
  { 
    count = 1;
    for(i = 0; i < m; i++)
    {
       if(record[2*i+1] == j)
       count++;
    }
    if(count > 1)
    {
       sum = sum -1;
    }
  }
  return(sum);
}
       

没有办法测试,就先发出来了.而且也不知道楼主说的时间的问题是什么意思,反正刚参加,就先写出来吧

/*
看了那么多,终于做了自己的第一次;
*/
#include "stdio.h"
char  IsInRecord( int *var,int count,int* record)
{
    int i;
    char mm;
    mm=0;
    for(i=0;i<count;i++)
    {
        if(record[i]==var[0])mm|=0x10;
        else if(record[i]==var[1])mm|=0x01;
        if(mm==0x11)return mm;
    }
    
    
    return mm;
}
int Religions(int n,int m,int* record)
{
    int count;
    int *RecordTemp;
    int *ptr;
    int max;
    int i;
    char revar;

    max=n;
    RecordTemp= (int *) malloc (n);
    ptr=record;
    count=0;
    for(i=0;i<m;i++,ptr+=2)
    {
        revar=IsInRecord(ptr,count,RecordTemp);
        if(revar==0x11)
        {
            
        }
        else if(revar==0x01)
        {
            RecordTemp[count]=ptr[0];
            count++;
            max--;
        }
        else if(revar==0x10)
        {
            RecordTemp[count]=ptr[1];
            count++;
            max--;
        }
        else 
        {
            RecordTemp[count]=ptr[0];
            count++;
            RecordTemp[count]=ptr[1];
            count++;
            max--;
        }
        
        
    }
    
    
    free(RecordTemp);
    return max;
    
}
int main()
{
    int i;
    int record[]=
    {
    1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,1,10
    };
    printf("\nThe result is ");   //不知道为什么，少了这一句的话，
                //例子里的第二个竟然没有结果的，
                //奇怪，
    i=Religions(10,9,record);
    printf("%d\n",i);
}

int Religions(int n,int m,int* record)
{
    
    int count(0), i;
    int *a=new int[n+1];
    for(i=1;i<n+1;i++)
      a[i]=0;  
    for(i=0;i<2*m;i+=2){
    if(!a[record[i]]&&!a[record[i+1]])
             count++;
       a[record[i]]=1;
       a[record[i+1]]=1;}       
     for(i=1;i<=n;i++)
       if(a[i]==0)
         count++;
    return count;
}  

#include <iostream>
using namespace std;
/*有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
返回值：最大可能的宗教数。
*/
int Religions(int n,int m,int* record)
{
    char *a = new char[n];
    int count = 0;
    for(int i = 0; i < m; i++)
    {
        if(a[record[i*2]-1]!=1&&a[record[i*2+1]-1]!=1)
            count++;
        a[record[i*2]-1]=a[record[i*2+1]-1]=1;
    }
    for(int i = 0; i < n; i++)
        if(a[i]!=1)
            count++;
    delete []a;
    return count;
}

int main(void)
{
    int n,m;
    n=10;
    m=4;
    int record[]=
   {2,3,
   4,5,
   4,8,
   5,8};
    cout << Religions(n,m,record) << endl;
    cin.get();
    return 0;
}

vc6.0编译通过！
第一部分：
#include<stdio.h>
#include<stdlib.h>

typedef struct Vnode{//定义一个结构体
        int num;
        int first;
       
        }Vnode;

int local(Vnode adjlist[],int num,int k){//判断数组结构中是否存在num
    for(int l=0;l<k;l++){
            if(adjlist[l].num==num)
            {return l;
            exit(0);
            }
            }
    
            return -2;
            }

第二部分
int Religions(int n,int m,int* record)
{
    int return1,return2,poss;
    int s,k,r,sort=0,count=0;
    Vnode *adjlist;

   
    if(2*m<n){s=2*m;
    }else{s=n;
          }
    adjlist=(Vnode *)malloc(sizeof(Vnode)*s);//开辟空间！
     for(int j=0;j<s;j++){
             
             adjlist[j].num=-3;
             adjlist[j].first=-3;
             }
 for(int jj=0;jj<m;jj++){
         k=2*jj;
         r=2*jj+1;
         return1=local(adjlist,record[k],count);
         return2=local(adjlist,record[r],count);
        /* if(return1==-2&&return2==-2) poss=1;
          if(return1!=-2&&return2!=-2) poss=2;
          if(return1!=-2) poss=3;
           if(return2!=-2) poss=4;*/
      if(return1==-2&&return2==-2){//如果两者都不存在 ，
                       adjlist[count].num=record[k];count++;
                       adjlist[count].num=record[r];
                       adjlist[count].first=adjlist[count-1].num;
                       count++;    
                      
                       }
         if(return1!=-2&&return2!=-2){//两者已经有
          if(adjlist[return1].first!=adjlist[return2].first&&adjlist[return1].first!=-3&&
              adjlist[return2].first!=-3)//两个存在数的first不相等且不等于初始值-3
          adjlist[adjlist[return1].first].first=adjlist[return2].first;
          if(adjlist[return1].first==-3&&adjlist[return2].first!=-3)//其中有一个为首个数
          {adjlist[return1].first=adjlist[return2].first;
          }
          if(adjlist[return2].first==-3&&adjlist[return1].first!=-3){//其中有一个为首个数
              adjlist[return2].first=adjlist[return1].first;
          }
          if(adjlist[return2].first==-3&&adjlist[return1].first==-3){//两个存在数都是首个数
              adjlist[return2].first=adjlist[return1].num;
          }continue;
                            }
                           else {
                                 if(return1!=-2){ //第一个存在
                                     adjlist[count].num=record[r];
                                                  adjlist[count].first=adjlist[return1].num;
                                                  count++;
                                                 
                                                 }
                                  if(return2!=-2){//第二个存在
                                      adjlist[count].num=record[k];
                                                  adjlist[count].first=adjlist[return2].num;
                                                  count++;
                                                 
                                                  }               
                                                
                                 
                                 }

 }
 count--;//加多了一个

 for(int ii=0;ii<count;ii++)
     if(adjlist[ii].first==-3) {sort++;}
 
 return (n-count-1+sort);//再减1是因为下标问题！
}

主函数

int main(){
    
int n=10, m=9,
record[]=
{1 ,2,
1 ,3,
1 ,4,
1 ,5,
1 ,6,
1 ,7,
1 ,8,
1 ,9,
1 ,10};
  
    printf("possiblle sort %d",Religions(n,m,record));
    return 0;

    }

怎么只有题目,没有答案呀，真晕.
[em18]