2062 . 分點問題（一）

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb a
中數理論
「因為時間與空間獨立，這些時空的聯合分布可以透過貝氏定理，找出先後的條件機率，並透過微積分找出體用的相對機率，即 PDF/PMF 或 CDF。」

User's AC Ratio

85.1% (57/67)

Submission's AC Ratio

42.3% (99/234)

Tags

CKcon 2018-CKcon-fin

Description

給定一張無向圖$G = \{V,E\}$，點由1編號到$N$，請找出兩個不相交點集$S,T$（即$S,T$沒有共同點），使得$S,T$都是$G$的邊覆蓋。
若$S$是一張圖$G$點集的子集，且圖中每一條邊都至少接觸$S$中的一個頂點，即稱$S$是$G$的邊覆蓋。

Input Format

第一行有兩個非負整數$N,M$，代表點數與邊數。
接下來的$M$行各代表圖上的一條邊，每行各有兩個正整數$u,v$代表該邊連接的頂點編號。

對於所有測資，$1 \leq N\leq 10^ 6; M \leq \min\left( \frac{N(N-1)}{2}, 2\times 10^ 6\right)$，且給定的圖是簡單圖（沒有自環或重邊）。

Output Format

第一行輸出兩個數字，分別代表點集$S$跟$T$的大小，
第二行輸出點集$S$的元素，第三行輸出點集$T$的元素。
如果無法找到，輸出-1。

Sample Input

2 1
1 2

Sample Output

1 1
1
2

Hints

注意：由於本題輸入/輸出十分龐大，使用C++作答的同學，請在程式碼開頭加上#include <cstdio>，並利用scanf讀入資料、用printf輸出資料。

scanf 常用的讀入方式如下：
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。

printf 常用的輸出方式如下：
printf("%d\n",x); 輸出一行包含一個int 型態變數x。
printf("%lld\n",y); 輸出一行包含一個long long 型態變數y。

Problem Source

Problem set by edisonhello
建國中學107學年度校隊選拔：複試pA

Subtasks

No. Testdata Range Constraints Score
1 0~17 $N \leq 10$ 9
2 0~27 $N \leq 20$ 13
3 0~42 $N \leq 3000$ 29
4 0~59 無額外限制 49

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 900 524288 262144 1 2 3 4
1 900 524288 262144 1 2 3 4
2 900 524288 262144 1 2 3 4
3 900 524288 262144 1 2 3 4
4 900 524288 262144 1 2 3 4
5 900 524288 262144 1 2 3 4
6 900 524288 262144 1 2 3 4
7 900 524288 262144 1 2 3 4
8 900 524288 262144 1 2 3 4
9 900 524288 262144 1 2 3 4
10 900 524288 262144 1 2 3 4
11 900 524288 262144 1 2 3 4
12 900 524288 262144 1 2 3 4
13 900 524288 262144 1 2 3 4
14 900 524288 262144 1 2 3 4
15 900 524288 262144 1 2 3 4
16 900 524288 262144 1 2 3 4
17 900 524288 262144 1 2 3 4
18 900 524288 262144 2 3 4
19 900 524288 262144 2 3 4
20 900 524288 262144 2 3 4
21 900 524288 262144 2 3 4
22 900 524288 262144 2 3 4
23 900 524288 262144 2 3 4
24 900 524288 262144 2 3 4
25 900 524288 262144 2 3 4
26 900 524288 262144 2 3 4
27 900 524288 262144 2 3 4
28 1900 524288 262144 3 4
29 1900 524288 262144 3 4
30 1900 524288 262144 3 4
31 1900 524288 262144 3 4
32 1900 524288 262144 3 4
33 1900 524288 262144 3 4
34 1900 524288 262144 3 4
35 1900 524288 262144 3 4
36 1900 524288 262144 3 4
37 1900 524288 262144 3 4
38 1900 524288 262144 3 4
39 1900 524288 262144 3 4
40 1900 524288 262144 3 4
41 1900 524288 262144 3 4
42 1900 524288 262144 3 4
43 2900 524288 262144 4
44 2900 524288 262144 4
45 2900 524288 262144 4
46 2900 524288 262144 4
47 2900 524288 262144 4
48 2900 524288 262144 4
49 2900 524288 262144 4
50 2900 524288 262144 4
51 2900 524288 262144 4
52 2900 524288 262144 4
53 2900 524288 262144 4
54 2900 524288 262144 4
55 2900 524288 262144 4
56 2900 524288 262144 4
57 2900 524288 262144 4
58 2900 524288 262144 4
59 2900 524288 262144 4
Submit
Status
Ranklist
Back to Top