TopCoder

輸光光

User's AC Ratio

81.4% (35/43)

38.6% (51/132)

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

第一行有兩個非負整數$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)$，且給定的圖是簡單圖（沒有自環或重邊）。

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

2 1
1 2

1 1
1
2

注意：由於本題輸入/輸出十分龐大，使用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 set by edisonhello
建國中學107學年度校隊選拔：複試pA

For Testdata: 0 ~ 17, Score: 9
For Testdata: 0 ~ 27, Score: 13
For Testdata: 0 ~ 42, Score: 29
For Testdata: 0 ~ 59, Score: 49

Submit

Status