結果

問題 No.1254 補強への架け橋
コンテスト
ユーザー beet
提出日時 2020-10-09 21:46:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 185 ms / 2,000 ms
コード長 1,468 bytes
コンパイル時間 2,130 ms
コンパイル使用メモリ 216,976 KB
最終ジャッジ日時 2025-01-15 04:22:42
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:53:15: warning: ‘cur’ may be used uninitialized [-Wmaybe-uninitialized]
   53 |   while(!G[cur].empty()){
      |               ^
main.cpp:48:7: note: ‘cur’ was declared here
   48 |   int cur;
      |       ^~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n;
  cin>>n;
  using P = pair<int, int>;
  map<P, int> idx;
  vector<set<int>> G(n);
  for(int i=0;i<n;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    if(!(a<b)) swap(a,b);
    idx[P(a,b)]=i+1;
    G[a].emplace(b);
    G[b].emplace(a);
  }
  queue<int> que;
  for(int i=0;i<n;i++) que.emplace(i);
  while(!que.empty()){
    int v=que.front();que.pop();
    if(G[v].size()!=1u) continue;
    int u=*G[v].begin();
    assert(G[u].count(v));
    G[v].erase(u);
    G[u].erase(v);
    que.emplace(u);
  }

  int cur;
  for(int i=0;i<n;i++)
    if(!G[i].empty()) cur=i;

  vector<int> es;
  while(!G[cur].empty()){
    int nxt=*G[cur].begin();
    es.emplace_back(idx[minmax({cur,nxt})]);
    assert(G[nxt].count(cur));
    G[cur].erase(nxt);
    G[nxt].erase(cur);
    cur=nxt;
  }
  sort(es.begin(),es.end());

  cout<<es.size()<<endl;
  for(int i=0;i<(int)es.size();i++){
    if(i) cout<<' ';
    cout<<es[i];
  }
  cout<<newl;
  return 0;
}
0