TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

給一張無向圖,請問是否存在一條路徑滿足每條邊經過恰好一次且每個點經過至少一次。如果存在,求一條滿足條件的路徑。
以下為提供的解法,但是卻得到 TLE,請在 edit distance 4 以內將該程式碼修改正確:

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int n,m; cin>>n>>m;
  int i,c,s;
  bool flag;
  vector<vector<pair<int,int>>> G(n);
  vector<int> d(n),v(n),u(m),ans;
  for(i=0;i<m;i++){
    int x,y; cin>>x>>y; --x; --y;
    G[x].push_back({y,i});
    G[y].push_back({x,i});
    d[x]++; d[y]++;
  }
  c=0; s=0;
  for(i=0;i<n;i++){
    if(d[i]&1) s=i,c++;
  }
  if(c!=0&&c!=2){
    cout<<"No\n";
    return 0;
  }
  function<void(int)> dfs=[&](int x){
    int i;
    v[x]=1;
    for(i=0;i<(int)G[x].size();){
      pair<int,int> cur=G[x][i++];
      if(!u[cur.second]){
        u[cur.second]=1;
        dfs(cur.first);
        ans.push_back(cur.second);
      }
    }
  };
  dfs(s);
  flag=1;
  for(i=0;i<n;i++){
    if(!v[i]){
      flag=0;
      break;
    }
  }
  if((int)ans.size()!=m||!flag){
    cout<<"No\n";
    return 0;
  }
  reverse(ans.begin(),ans.end());
  cout<<"Yes\n";
  cout<<s+1<<"\n";
  for(i=0;i<m;i++)
    cout<<ans[i]+1<<" \n"[i+1==m];
  return 0;
}

Input Format

第一行輸入兩個正整數 $N,M$ 分別是點和邊的數量。

接下來有 $M$ 行每行兩個正整數 $x_i,y_i$ 代表第 $i$ 條邊是一條連接 $x_i$ 和 $y_i$ 的邊。

圖中可能有重邊和自環。

  • $1\le N\le 2\times 10^ 5$
  • $1\le M\le 5\times 10^ 5$
  • $1\le x_i,y_i\le N$

Output Format

如果該路徑不存在輸出一行 No

如果存在的話,第一行輸出 Yes,第二行輸出一個正整數代表路徑的起點 $s$,第三行輸出 $M$ 個正整數 $e_i$ 分別代表依序經過的邊的編號。

Sample Input 1

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

Sample Output 1

Yes
3
3 2 1 5 7 4 6

Sample Input 2

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

Sample Output 2

No

Sample Input 3

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

Sample Output 3

No

Hints

Problem Source

IOICamp 2023 Day1 pI

Subtasks

No. Testdata Range Score
1 0~70 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1
1 2000 524288 65536 1
2 2000 524288 65536 1
3 2000 524288 65536 1
4 2000 524288 65536 1
5 2000 524288 65536 1
6 2000 524288 65536 1
7 2000 524288 65536 1
8 2000 524288 65536 1
9 2000 524288 65536 1
10 2000 524288 65536 1
11 2000 524288 65536 1
12 2000 524288 65536 1
13 2000 524288 65536 1
14 2000 524288 65536 1
15 2000 524288 65536 1
16 2000 524288 65536 1
17 2000 524288 65536 1
18 2000 524288 65536 1
19 2000 524288 65536 1
20 2000 524288 65536 1
21 2000 524288 65536 1
22 2000 524288 65536 1
23 2000 524288 65536 1
24 2000 524288 65536 1
25 2000 524288 65536 1
26 2000 524288 65536 1
27 2000 524288 65536 1
28 2000 524288 65536 1
29 2000 524288 65536 1
30 2000 524288 65536 1
31 2000 524288 65536 1
32 2000 524288 65536 1
33 2000 524288 65536 1
34 2000 524288 65536 1
35 2000 524288 65536 1
36 2000 524288 65536 1
37 2000 524288 65536 1
38 2000 524288 65536 1
39 2000 524288 65536 1
40 2000 524288 65536 1
41 2000 524288 65536 1
42 2000 524288 65536 1
43 2000 524288 65536 1
44 2000 524288 65536 1
45 2000 524288 65536 1
46 2000 524288 65536 1
47 2000 524288 65536 1
48 2000 524288 65536 1
49 2000 524288 65536 1
50 2000 524288 65536 1
51 2000 524288 65536 1
52 2000 524288 65536 1
53 2000 524288 65536 1
54 2000 524288 65536 1
55 2000 524288 65536 1
56 2000 524288 65536 1
57 2000 524288 65536 1
58 2000 524288 65536 1
59 2000 524288 65536 1
60 2000 524288 65536 1
61 2000 524288 65536 1
62 2000 524288 65536 1
63 2000 524288 65536 1
64 2000 524288 65536 1
65 2000 524288 65536 1
66 2000 524288 65536 1
67 2000 524288 65536 1
68 2000 524288 65536 1
69 2000 524288 65536 1
70 2000 524288 65536 1