Language: C++


/// @file up.cc
/// @brief up の実装ファイル
/// @author Yusuke Matsunaga (松永 裕介)
///
/// Copyright (C) 2019 Yusuke Matsunaga
/// All rights reserved.


#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <list>

using namespace std;

class MFSetCell
{
public:

  long mId;

  MFSetCell* mParent;

  long mRank;

};

class MFSet
{
public:

  MFSet(long num);

  ~MFSet() = default;

  long
  find(long id);

  int
  merge(long id1,
	long id2);


private:

  MFSetCell*
  _find_top(MFSetCell* cell);

  vector<MFSetCell> mArray;

};


MFSet::MFSet(long num) :
  mArray(num)
{
  for ( long i = 0; i < num; ++ i ) {
    MFSetCell& cell = mArray[i];
    cell.mId = i;
    cell.mParent = &cell;
    cell.mRank = 0;
  }
}

long
MFSet::find(long id)
{
  auto tmp = &mArray[id];
  auto top = _find_top(tmp);
  return top->mId;
}

MFSetCell*
MFSet::_find_top(MFSetCell* cell)
{
  auto parent = cell->mParent;
  while ( parent->mParent != parent ) {
    cell = cell->mParent = parent->mParent;
    parent = cell->mParent;
  }
  return parent;
}

long
MFSet::merge(long id1,
	     long id2)
{
  auto cell1 = &mArray[id1];
  auto cell2 = &mArray[id2];

  if ( cell1->mParent != cell1 ) {
    cell1 = _find_top(cell1);
  }
  if ( cell2->mParent != cell2 ) {
    cell2 = _find_top(cell2);
  }
  if ( cell1 == cell2 ) {
    return cell1->mId;
  }

  if ( cell1->mRank > cell2->mRank ) {
    cell2->mParent = cell1;
    return cell1->mId;
  }
  else if ( cell1->mRank == cell2->mRank ) {
    ++ cell1->mRank;
    cell2->mParent = cell1;
    return cell1->mId;
  }
  else {
    cell1->mParent = cell2;
    return cell2->mId;
  }
}

void
no()
{
  cout << "No" << endl;
  exit(0);
}

void
yes()
{
  cout << "Yes" << endl;
  exit(0);
}

int
main(int argc,
     char** argv)
{
  cin.tie(0);
  ios::sync_with_stdio(0);

  long N;
  long M;
  long Q;
  cin >> N
      >> M
      >> Q;

  if ( Q == 0 ) {
    abort();
  }
  if ( M > ((N * (N - 1)) / 2) ) {
    abort();
  }

  MFSet mfset(N);

  vector<pair<long, long>> single_pair_list;
  vector<pair<long, long>> multi_pair_list;
  bool has_single = false;
  for ( long i = 0; i < Q; ++ i ) {
    long a, b, c;
    cin >> a >> b >> c;
    if ( c == 0 ) {
      single_pair_list.push_back(make_pair(a, b));
      mfset.merge(a, b);
      has_single = true;
    }
    else {
      multi_pair_list.push_back(make_pair(a, b));
    }
  }

  if ( M == N - 1 ) {
    // M = N - 1 の時は木構造のグラフとなる．
    if ( multi_pair_list.size() > 0 ) {
      // その場合複数経路はありえない．
      no();
    }
    else {
      yes();
    }
  }

  if ( !has_single ) {
    yes();
  }

  for ( auto p: multi_pair_list ) {
    long a = p.first;
    long b = p.second;
    if ( mfset.find(a) == mfset.find(b) ) {
      no();
    }
  }

  long K = 0;
  for ( long i = 0; i < N; ++ i ) {
    if ( mfset.find(i) == i ) {
      ++ K;
    }
  }

  long M_max = N - K + (K * (K - 1)) / 2;
  if ( M > M_max ) {
    no();
  }

  yes();

  return 0;
}


Compiler output:
a.cc:86:1: error: no declaration matches 'long int MFSet::merge(long int, long int)'
   86 | MFSet::merge(long id1,
      | ^~~~~
a.cc:41:3: note: candidate is: 'int MFSet::merge(long int, long int)'
   41 |   merge(long id1,
      |   ^~~~~
a.cc:29:7: note: 'class MFSet' defined here
   29 | class MFSet
      |       ^~~~~