1 #include<cstdio>
2 #define INF 0x7FFFFFFF
3 #define MAXN 1000010
4 int n, m, size;
5 int L[MAXN], R[MAXN], U[MAXN], D[MAXN], H[MAXN];
6 int S[MAXN], C[MAXN], X[MAXN], Q[MAXN];
7 void Init() {
8 int i;
9 for (i =
0; i <= m; i++
) {
10 S[i] =
0;
11 L[i +
1] =
i;
12 R[i] = i +
1;
13 U[i] = D[i] =
i;
14 }
15 R[m] =
0;
16 size = m +
1;
17 }
18 void Remove(
int c) {
19 int i, j;
20 R[L[c]] =
R[c];
21 L[R[c]] =
L[c];
22 for (i = D[c]; i != c; i =
D[i]) {
23 for (j = R[i]; j != i; j =
R[j]) {
24 D[U[j]] =
D[j];
25 U[D[j]] =
U[j];
26 S[C[j]]--
;
27 }
28 }
29 }
30 void Resume(
int c) {
31 int i, j;
32 R[L[c]] =
c;
33 L[R[c]] =
c;
34 for (i = D[c]; i != c; i =
D[i]) {
35 for (j = R[i]; j != i; j =
R[j]) {
36 U[D[j]] =
j;
37 D[U[j]] =
j;
38 S[C[j]]++
;
39 }
40 }
41 }
42 void Link(
int r,
int c) {
43 S[c]++
;
44 D[size] =
D[c];
45 U[size] =
c;
46 U[D[c]] =
size;
47 D[c] =
size;
48 if (H[r] <
0)
49 H[r] = L[size] = R[size] =
size;
50 else {
51 L[size] =
H[r];
52 R[size] =
R[H[r]];
53 L[R[H[r]]] =
size;
54 R[H[r]] =
size;
55 }
56 C[size] =
c;
57 X[size++] =
r;
58 }
59 bool Dance(
int now) {
60 int i, j, c, temp;
61 if (R[
0] ==
0) {
62 printf(
"%d", now);
63 for (i =
0; i < now; i++
)
64 printf(
" %d", X[Q[i]]);
65 putchar(
'\n');
66 return true;
67 }
68 for (temp = INF, i = R[
0]; i; i =
R[i]) {
69 if (S[i] <
temp) {
70 c =
i;
71 temp =
S[i];
72 }
73 }
74 Remove(c);
75 for (i = D[c]; i != c; i =
D[i]) {
76 Q[now] =
i;
77 for (j = R[i]; j != i; j =
R[j])
78 Remove(C[j]);
79 if (Dance(now +
1))
80 return true;
81 for (j = L[i]; j != i; j =
L[j])
82 Resume(C[j]);
83 }
84 Resume(c);
85 return false;
86 }
87 int main() {
88 int i, j, k;
89 while (~scanf(
"%d%d", &n, &
m)) {
90 Init();
91 for (i =
1; i <= n; i++
) {
92 H[i] = -
1;
93 scanf(
"%d", &
k);
94 while (k--
) {
95 scanf(
"%d", &
j);
96 Link(i, j);
97 }
98 }
99 if (!Dance(
0))
100 puts(
"NO");
101 }
102 return 0;
103 }
转载于:https://www.cnblogs.com/DrunBee/archive/2012/07/22/2604209.html
相关资源：数据结构—成绩单生成器
