这个题看起来是noi的食物链的化简版，同样用并查集，也直接套用“建立环并想办法摞在一起”。参见北极天南星的解题报告。
　　被一个学生选过的两门课互称为opposite。接到一个学生的选课单后：
　　如果两门课的根（根就是并查集中的根）相同，那就no answer了；
　　如果不同，首先检查这两门课是否都已经有了opposite，没有的话给没有opposite的课建立一下opposite，然后将第一门课的根合并到第二门课的根的opposite的根，同时将第二门课的根合并到第一门课的根的opposite的根。
　　这样做完后，课程不一定只被分成两群，但一个群只与另外一个群具有制约关系。
　　题目要求输出第一天最少要安排几门考试，可以贪心做。把两个具有opposite关系的群中科目较少的那个安排到day1考。
　　Submit 1: RTE on 6。这篇解题手记没有体现程序的细节，写的很不好，细节上出了一点问题，却实在没有办法在这里描述了。但这个问题因该造成WA而不是RTE，所以RTE的原因仍然没有找到。生成一下大数据。小数据就出错了，有些课程没有人选时就出问题了，把没人选的课统统放在第二天考就行了。
　　Submit 2: WA on 11。去掉“第一天安排的科目最少”。
　　MaShuo提出并查集的算法有问题。听完我讲的方法后，又找不出问题了。但提供了一个重要的信息：题目虽有must be held on first day，但实际并不要求第一天安排的科目最少。
　　Submit 3: WA on 6。做完将课程分群的工作后，要把若干对有opposite关系的群合并成两个，而我合并时只抓住opposite的一边合并，另一边不管（这个叙述不好）。
　　Submit 4: WA on 6。合并时opposite关系处理的不对。
　　Submit 5: PE on 1。少打了个yes。
　　Submit 6: AC。终于AC了。继续查加了“第一天安排的科目最少”的版本为什么不对。不对的原因同Submit 4。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

//AC
#include <cstdio>
using namespace std;
 
struct course
{
    course *oppo,*r;
    bool choose;
    inline course* root()
    {
        while (r!=r->r) r=r->r;
        return r;
    }
    inline void uni(course *p)
    {
        r=p;
    }
    course():oppo(0),r(this),choose(false){};
};
 
int main()
{
    course courses[201];
    int n,m;
    scanf("%d%d",&n,&m);
    for (;m;--m)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if (courses[a].root()==courses[b].root())
        {
            printf("no\n"); return 0;
        }
        else
        {
            courses[a].choose=courses[b].choose=true;
            if (!courses[a].oppo) courses[a].oppo=&courses[b];
            if (!courses[b].oppo) courses[b].oppo=&courses[a];
            course *rora=courses[a].root()->oppo->root();
            course *rorb=courses[b].root()->oppo->root();
            courses[a].root()->uni(rorb); courses[b].root()->uni(rora);
        }
    }
    int i(1),nday1(0);
    for (;!courses[i].choose;++i);
    course day1; day1.oppo=courses[i].root()->oppo->root();
    courses[i].root()->uni(&day1);
    for (;i<=n;++i)
        if (courses[i].choose)
            if (courses[i].root()==&day1) ++nday1;
            else if (courses[i].root()->oppo->root()!=&day1)
            {
                courses[i].root()->uni(&day1); courses[i].root()->oppo->root()->uni(day1.oppo); 
                ++nday1;
            }
    printf("yes\n%d\n",nday1);
    for (i=1;i<=n;++i)
        if (courses[i].root()==&day1)
        {            
            printf("%d ",i);
        }
    printf("\n");
    return 0;
}