fork(5) download 
  1. /* @author: Praveen Dhinwa */
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long LL;
  5. #define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
  6. #define rep1(i,a,b) for(int (i)=(a);(i)<=(int)(b);(i)++)
  7. #define fore(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  8.  
  9. using namespace std;
  10.  
  11. const int N = (int) 1e5 + 5;
  12. vector <int> g[N];
  13. set <pair <int, int> > blocked;
  14.  
  15. int dfs (int v) {
  16.   vector <int> adj;
  17.   for (int i = 0; i < g[v].size(); i++) if (blocked.find (make_pair (g[v][i], v)) == blocked.end()) adj.push_back(g[v][i]);
  18.   for (int i = 0; i < adj.size(); i++) {
  19.     int u = adj[i];
  20.     blocked.insert (make_pair (u, v));
  21.     blocked.insert (make_pair (v, u));
  22.   }
  23.   vector <int> unpaired;
  24.   for (int i = 0; i < adj.size(); i++) {
  25.     int u = adj[i];
  26.     int w = dfs (u);
  27.     if (w != 0) unpaired.push_back(w);
  28.   }
  29.   cout << unpaired.size() << endl;
  30.   for (int i = 0; i + 1 < unpaired.size(); i += 2) {
  31.     int u = unpaired[i], w = unpaired[i + 1];
  32.     printf ("%d %d %d\n", u, v, w);
  33.   }
  34.   if (unpaired.size() % 2 == 1) {
  35.     return unpaired[unpaired.size() - 1];
  36.   } else return 0;
  37. }
  38.  
  39. int main() {
  40.   int n, m;
  41.   scanf ("%d %d", &n, &m);
  42.   for (int i = 0; i < m; i++) {
  43.     int u, v;
  44.     scanf ("%d %d", &u, &v);
  45.     g[u].push_back (v);
  46.     g[v].push_back (u);
  47.   }
  48.   if (m & 1) cout << -1 << endl;
  49.   else dfs (1);
  50.   return 0;
  51. }
  52.  
Success #stdin #stdout 0s 4476KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/Ny9PjL
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!