給一張無向圖,請問是否存在一條路徑滿足每條邊經過恰好一次且每個點經過至少一次。如果存在,求一條滿足條件的路徑。
以下為提供的解法,請構造出一筆滿足題目條件的測資讓該程式碼無法通過(WA / RE / TLE 2s):
#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;
}
第一行輸入兩個正整數 $N,M$ 分別是點和邊的數量。
接下來有 $M$ 行每行兩個正整數 $x_i,y_i$ 代表第 $i$ 條邊是一條連接 $x_i$ 和 $y_i$ 的邊。
圖中可能有重邊和自環。
如果該路徑不存在輸出一行 No
。
如果存在的話,第一行輸出 Yes
,第二行輸出一個正整數代表路徑的起點 $s$,第三行輸出 $M$ 個正整數 $e_i$ 分別代表依序經過的邊的編號。
以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料:
#include<stdio.h>
int main(){
printf("%d %d\n",3,3);
printf("1 2\n");
printf("2 3\n");
printf("3 1\n");
}
IOICamp 2023 Day1 pG
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |