Submission #1386205

---

Source Code Expand

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

#define int long long

#define inf 1000000007LL
#define mod 1000000007LL

#define rep(i, n) for(int i = 0; i < (n); i++)
#define trep(i, n) for(int i = 0; i <= (n); i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define mfor(i, s, t) for(int i = (s); i < (t); i++)
#define tfor(i, s, t) for(int i = (s); i <= (t); i++)
#define rfor(i, s, t) for(int i = (t) - 1; i >= (s); i--)

vector<int> v[2][334334];
bool tmp[334334];
int coun[334334];
bool sude[2][334334];

void dfs(int s, int p) {
  if(!sude[s][p]) {
    sude[s][p] = true;
    for(auto i : v[s][p]) {
      dfs(s, i);
    }
  }
}

signed main() {
  int n, m;
  cin >> n >> m;
  rep(i, n * 2) {
    tmp[i] = true;
    sude[0][i] = false;
    sude[1][i] = false;
  }
  int all = 0;
  rep(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    if(c) {
      tmp[a] = false;
      tmp[b] = false;
      v[0][b].push_back(a);
      v[1][a].push_back(b);
      coun[a] = b;
      coun[b] = a;
    }
    else {
      v[0][a].push_back(b);
      v[1][b].push_back(a);
    }
    all += c;
  }
  rep(i, n) {
    if(tmp[i * 2]) {
      dfs(0, i * 2);
    }
    if(tmp[i * 2 + 1]) {
      dfs(1, i * 2 + 1);
    }
  }
  cout << all << endl;
  rep(i, n) {
    if(!sude[0][i * 2]) {
      sude[0][i * 2] = true;
      dfs(1, coun[i * 2]);
      cout << i * 2 + 1 << endl;
    }
    if(!sude[1][i * 2 + 1]) {
      sude[1][i * 2] = true;
      dfs(0, coun[i * 2 + 1]);
      cout << i * 2 + 2 << endl;
    }
  }
}

Submission Info

Judge Result