2016年2月25日 星期四

[HOJ 293][Codeforces #192]Graph Reconstruction (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 293 - Graph Reconstruction

Special Judge

Problem Statistics
Solved Member: 18  Submission: 121  User Tried: 19
Problem:
給定一張簡單無向圖,點編號為 1 至 n ,且每個點的度數不超過2,對於任意點對,最多只會有一條邊相連,且沒有自己連自己的邊。

現在你要構造一張新的圖,並滿足以下條件:

  • 新圖的點數與邊數與原圖一樣多。
  • 必須滿足第一段所敘述的條件。
  • 原圖所出現的邊,新圖不能出現。
Input:
第一行有兩個數字 n m (1 ≤ m ≤ n ≤ 105),接下來有m行,每行兩個數字u v,表示點u與點v有一條連邊。
Output:
如果沒有解輸出-1,否則輸出恰好 m 行,表示新圖的 m 條邊。

若有多組解,輸出任意一組即可。
Sample Input:
Sample #1:
8 7
1 2
2 3
4 5
5 6
6 8
8 7
7 4

Sample #2:
3 2
1 2
2 3

Sample #3:
5 4
1 2
2 3
3 4
4 1
Sample Output:
Sample #1:
1 4
4 6
1 6
2 7
7 5
8 5
2 8

Sample #2:
-1

Sample #3:
1 3
3 5
5 2
2 4
HINT:
Sample #1:
輸入圖:


輸出圖:


Sample #3:
輸入圖:


輸出圖:

Source:
Codeforces #192
Problem Setter
hanhan0912
Testdata:
TestTimeMemoryScore
0-12000ms262144kb
0-22000ms262144kb
0-32000ms262144kb
1-12000ms262144kb10
1-22000ms262144kb
1-32000ms262144kb
1-42000ms262144kb
1-52000ms262144kb
2-12000ms262144kb10
2-22000ms262144kb
2-32000ms262144kb
2-42000ms262144kb
2-52000ms262144kb
3-12000ms262144kb10
3-22000ms262144kb
3-32000ms262144kb
3-42000ms262144kb
3-52000ms262144kb
4-12000ms262144kb10
4-22000ms262144kb
5-12000ms262144kb10
5-22000ms262144kb
5-32000ms262144kb
62000ms262144kb10
72000ms262144kb10
8-12000ms262144kb10
8-22000ms262144kb
8-32000ms262144kb
9-12000ms262144kb10
9-22000ms262144kb
9-32000ms262144kb
9-42000ms262144kb
9-52000ms262144kb
10-12000ms262144kb10
10-22000ms262144kb
10-32000ms262144kb
10-42000ms262144kb
10-52000ms262144kb

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原