2062 . 分點問題（一）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

88.8% (95/107)

Submission's AC Ratio

42.2% (158/374)

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≤N≤106;M≤min(N(N−1)2,2×106)，且給定的圖是簡單圖（沒有自環或重邊）。

Output Format

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

Sample Input 1

2 1
1 2

Sample Output 1

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≤10 9
2 0~27 N≤20 13
3 0~42 N≤3000 29
4 0~59 無額外限制 49

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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
Back to Top