이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
using namespace std;
int ct = 0;
vector<int> res;
vector<bool> b;
bool dfs(int c, int p,vector<vector<int>> &g) {
res.push_back(c);
ct++;
int r = true;
int coun = 0;
bool h = false;
for(auto i:g[c]) {
if(g[i].size()==1) h=true;
}
if(h) ct++;
b.push_back(h);
for(auto i:g[c]) {
if(i==p) continue;
if(g[i].size()==1) continue;
r&=dfs(i,c,g);
coun++;
}
if(coun>1) return false;
return r;
}
int main()
{
int n,m; cin>>n>>m;
if(m!=n-1) {
cout<<"NO"<<endl;
exit(0);
}
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int x,y; cin>>x>>y; x--; y--;
g[x].push_back(y);
g[y].push_back(x);
}
if(n==2) {
cout<<"YES"<<endl;
cout<<"2"<<endl;
cout<<"1 1"<<endl;
exit(0);
}
int cur = 0;
while(true) {
if(cur==n) break;
if(g[cur].size()==1) {cur++; continue;}
int coun = 0;
for(int i : g[cur]) if(g[i].size()!=1) coun++;
if(coun==1) break;
cur++;
}
if(cur==n) {
cur = 0;
while(true) {
if(g[cur].size()!=1) break;
cur++;
}
cout<<"YES"<<endl;
cout<<2<<endl;
cout<<(cur+1)<< " "<<(cur+1)<<endl;
}else {
if(!dfs(cur,-1,g)) {
cout<<"NO"<<endl;
}else {
cout<<"YES"<<endl;
cout<<res.size()*2<<endl;
for (int i = 0; i < res.size()-1; ++i) {
cout<<res[i]+1<<" ";
if(true) cout<<res[i]+1<<" ";
}
cout<<res[res.size()-1]+1;
if(true) cout<<" "<<res[res.size()-1]+1;
cout<<endl;
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
newspapers.cpp: In function 'int main()':
newspapers.cpp:71:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int i = 0; i < res.size()-1; ++i) {
| ~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |