TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

87.8% (36/41)

Submission's AC Ratio

49.0% (74/151)

Tags

Description

還記得大陸人嗎?
「操作分治主要用途是结合其它几种方法来解决高维偏序问题(竞赛中常见的主要是三维偏序问题)」
那麼什麼是偏序呢?

我們說一個定義在一個集合$X$上的關係$\leq$是一個「偏序關係」,如果以下三條式子滿足:
一、自反性:$\forall x\in X,x\leq x$
二、反對稱性:$\forall x,y\in X, [x\leq y\wedge y\leq x]\Rightarrow x=y$
三、傳遞性:$\forall x,y,z\in X,[x\leq y\wedge y\leq z]\Rightarrow x\leq z$
簡單來說,任何一個元素都小於等於自己本身。如果兩個元素互相小於等於,那麼他們就是同一個元素。如果甲小於等於乙,乙又小於等於丙,那麼甲也小於等於丙。

既然理解什麼是偏序了,那就馬上來一題試試身手吧!

$X$中有一些元素$x_1, x_2, \dots, x_n$(不一定相異)使得$X=\{x_i|1\leq i\leq n\}$。令$\leq$是定義在$X$上的偏序關係。已知$(X,\leq)$是全序集(也就是,對於所有$X$中的任兩個元素$x,y$,$x\leq y$和$y\leq x$至少有一者成立)。給定一些$x_1,x_2,\dots,x_n$之間的偏序關係,請計算$|X|$的最大值,並給出其中一個達到最大值的偏序關係。

Input Format

第一行包含兩個正整數$n\leq 10^ 6, m\leq 10^ 6$,代表(不一定相異的)元素個數以及給定的偏序關係個數。
之後的$m$行,每行會有兩個正整數$1\leq i,j\leq n$,代表$x_i\leq x_j$。保證不會有重複的偏序關係。

子任務(測資) 額外限制 分數
1 (0~4) $n\leq 800$ 21
2 (5~9) $n,m\leq 10^ 4$ 36
3(0~14) 43

Output Format

請輸出兩行。第一行含有一個正整數$k$,代表$|X|$的最大值。第二行含有$n$個1到$k$的正整數,代表其中一個達到最大值的偏序關係。這裡第$i$個數是$r_i$的意思是$x_i$在$X$中是第$r_i$小的。若仍不理解,請見範例輸出輸入。

Sample Input 1

4 5
1 2
2 3
3 4
3 2
1 4

Sample Output 1

3
1 2 2 3

Hints

範例測資中,$x_2\leq x_3$且$x_3\leq x_2$,故$x_2=x_3$,也就是說相異元素個數至多3個。而令$x_1$是第一小,$x_2,x_3$是第二小,$x_4$是第三小(也就是說$x_1\leq x_2= x_3\leq x_4$)時符合所有給定的偏序關係。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第六次模擬賽pB

Subtasks

No. Testdata Range Score
1 0~4 21
2 5~9 36
3 0~14 43

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 1048576 262144 1 3
1 1000 262144 262144 1 3
2 1000 262144 262144 1 3
3 1000 262144 262144 1 3
4 1000 262144 262144 1 3
5 1000 262144 262144 2 3
6 1000 262144 262144 2 3
7 1000 262144 262144 2 3
8 1000 262144 262144 2 3
9 1000 262144 262144 2 3
10 2000 262144 262144 3
11 2000 262144 262144 3
12 2000 262144 262144 3
13 2000 262144 262144 3
14 2000 262144 262144 3