undirected-tree-validator.cpp 1.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
  1. #include "testlib.h"
  2. #include <iostream>
  3. #include <sstream>
  4. #include <fstream>
  5. #include <iomanip>
  6. #include <string>
  7. #include <cstdlib>
  8. #include <cstdio>
  9. #include <cstring>
  10. #include <cmath>
  11. #include <ctime>
  12. #include <climits>
  13. #include <cassert>
  14. #include <vector>
  15. #include <queue>
  16. #include <stack>
  17. #include <deque>
  18. #include <set>
  19. #include <map>
  20. #include <bitset>
  21. #include <utility>
  22. #include <algorithm>
  23. #define forn(i, n) for (int i = 0; i < int(n); i++)
  24. using namespace std;
  25. int leader(vector<int>& dsu, int idx)
  26. {
  27. return dsu[idx] == idx ? dsu[idx] : (dsu[idx] = leader(dsu, dsu[idx]));
  28. }
  29. bool merge(vector<int>& dsu, int a, int b)
  30. {
  31. a = leader(dsu, a);
  32. b = leader(dsu, b);
  33. if (a == b)
  34. return false;
  35. else
  36. {
  37. if (rnd.next(2) == 0)
  38. dsu[a] = b;
  39. else
  40. dsu[b] = a;
  41. return true;
  42. }
  43. }
  44. int main()
  45. {
  46. registerValidation();
  47. int n = inf.readInt(2, 100000, "n");
  48. inf.readEoln();
  49. vector<int> dsu(n);
  50. forn(i, n)
  51. dsu[i] = i;
  52. set<pair<int,int> > edges;
  53. forn(i, n - 1)
  54. {
  55. int x = inf.readInt(1, n, "x_i");
  56. inf.readSpace();
  57. int y = inf.readInt(1, n, "y_i");
  58. inf.readEoln();
  59. ensuref(x != y, "Tree can't contain loops");
  60. ensuref(edges.count(make_pair(x, y)) == 0, "Tree can't contain multiple edges between a pair of vertices");
  61. edges.insert(make_pair(x, y));
  62. edges.insert(make_pair(y, x));
  63. ensuref(merge(dsu, x - 1, y - 1), "Tree can't contain cycles");
  64. }
  65. inf.readEof();
  66. return 0;
  67. }