提出 #62561474

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define v vector
constexpr int N = 2e5 + 5;

vi components;
v<vi> edges;
v<pii> adj[N];
bool vis[N];

void dfs(int p, int u, int comp) {
  vis[u] = 1;

  for(const auto& e : adj[u]) {
    if(e.first != p) {
      if(vis[e.first]){
        edges.push_back({comp, e.first, e.second});
      } else {
        dfs(u, e.first, comp);
      }
    }
  }
}

void solve(){
  int n, m;
  cin >> n >> m;

  rep(i, 0, m){
    int a, b; cin >> a >> b;
    adj[a].push_back({b, i + 1});
    if(a != b){
      adj[b].push_back({a, i + 1});
    }
  }


  rep(i, 1, n + 1){
    if(!vis[i]){
      components.push_back(i);
      dfs(-1, i, i);
    }
  }


  
  cout << sz(components) - 1 << '\n';
  if(sz(components) > 1){

    queue<int> left;
    auto edge = edges.back();

    rep(i, 0, sz(components)){
      if(components[i] != edge[0]){
        left.push(components[i]);
      }
    }

    while(sz(left)){
      edge = edges.back();
      if(left.front() == edge[2]){
        left.push(left.front());
        left.pop();
        continue;
      }

      cout << edge[2] << ' ' << edge[1] << ' ' << left.front() << '\n';
      left.pop();
      edges.pop_back();
    }


  }

}

int main(){
  // ios_base::sync_with_stdio(false), cin.tie(NULL);
  // int t; cin >> t; while(t--)
  solve();
  return 0;
}

提出情報

ジャッジ結果