SGU 172 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=172

172.eXam

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

In Russia school pupils must do some exams before leaving school. Among others, they must do two "selective" exams. This means that school provides a list of available subjects; each pupil selects two different subjects from this list and is going to do this exams. According to rules, pupil isn't allowed to do both exams at the same day, so the school must schedule the exams, i.e. provide some days when pupils will be able to do exams.

在俄罗斯学校里,小学生在离校之前必须做两个考试。这意味着学校必须提供一些可选的考试。每个学生选择两个不同的项目。根据规则每个学生不允许在同一天完成两个考试。所以学校必须安排好这些考试。

One school does not want to warn teachers too much. They want to schedule all the exams into two days in such way that exams on some subjects are on the first day, and exams on all other (and only on them) are on second. You are to write a program, which will determine, if it is possible to schedule exams in this way so that all pupils will be able to do all their selected exams.

一个学校不想让老师太辛苦,他们想在两天之内安排所有这些考试。在第一天安排一些考试,在第二天也只能在第二天安排其它的考试。你被安排写一个这样的程序来看看是否可以做到让每个学生都能参加他们的考试。

Input

On the first line of input there are two integers N and M (1<=N<=200, 1<=M<=30000) - the number of available subjects and the number of pupils. Then M lines follows; on i-th of them there are two integers - the numbers of exams, which were selected by i-th pupil. Exams are numerated from 1 to N.

在第一行有两个整数N和M,(1<=N<=200,1<=m<=30000)N代表可选择的考试的科目数,M代表学生的人数。下面的M行中分别代表一个学生选择的考试项目数。

Output

If the solution exists, write on the first line of output only one word "yes". On the second line write the total number of exams, which must be held on first day, and on the third line - the numbers of subjects of this exams. If there exist several solutions, output any. If no solution exists, write to output only one word "no".

如果安排方法存在,在第一行写"yes",在第二行输出在第一天必须安排的考试项目的数量,在第三行输出考试项目的项目数。如果存在多个安排方法,输出其中一个就可以了。如果安排方法不存在,输出"no"

Sample Input

4 4
1 2
3 4
2 4
1 3

Sample Output

yes
2
1 4

真的只有会做的题才会觉得是水题,做起来刚开始感觉还是挺复杂的,网络上有很多种解法,我用的是并查集,不过一直WA on test 6,查了很久才发现问题在于合并具有对立关系的集合时出错。

被同一个学生选中的两门课就是具有对立关系的两个元素。如果两个元素还未属于任何集合,那么就把这两个元素作为两个新的对立集合。如元素x,y则用D[x]=y;D[y]=x;表示这两个元素具有对立关系。

如果元素x属于某个集合,元素y是独立的元素,就把元素x的对立集合与元素y合并。Union(y,D[x]);
用并查集处理数据会生成许多对具有对立关系的集合,输出某个集合,同时标记它的对立集合的元素,直到处理完所有元素。

(注:翻译来自http://allenfw.ycool.com/post.643367.html

CODE

#include<stdio.h>
#include<string.h>
 
int pre[201],D[201];
 
void Init(int n)
{
  for(int i=0;i<=n;++i){
      pre[i]=i;
      D[i]=0;
  }
}
 
int Find(int x)
{
  int r=x,t;
  while(x!=pre[x]) x=pre[x];
  while(r!=x){
      t=pre[r];
      pre[r]=x;
      r=t;
  }
  return x;
}
 
void Union(int a,int b)
{
  a=Find(a);
  b=Find(b);
  pre[a]=b;
}
 
int main()
{
  int i,j,k,n,m,x,y;
  scanf("%d%d",&n,&m);
  Init(n);
  bool flag=false;
  while(m--){
      scanf("%d%d",&x,&y);
      if(flag) continue;
      if(Find(x)==Find(y)) flag=true;
 
      if(D[x]==0)
	D[x]=y;
      else
	Union(y,D[x]);
 
      if(D[y]==0)
	D[y]=x;
      else
	Union(x,D[y]);
  }
 
  if(flag) puts("no");
  else{
      puts("yes");
      int ans[201],t;
      for(i=1,k=0;i<=n;i++){
	  if(D[i]){
	      ans[++k]=i;
	      t=Find(i);
	      for(j=i+1;j<=n;j++){
		  if(t==Find(j)){
		      ans[++k]=j;
		      D[j]=0;
		  }
	      }
	      t=Find(D[i]);
	      for(j=i+1;j<=n;j++)
		if(t==Find(j)) D[j]=0;
	  }
      }
      printf("%dn",k);
      for(i=1;i<=k;i++)
	printf("%d ",ans[i]);
      putchar('n');
  }
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:
发表评论?

0 条评论。

发表评论

注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>