Guest User

Untitled

a guest
Mar 17th, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.30 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 1005;
  6. int tree[maxn] = {0}, enemy[maxn][maxn] = {0}, n, m, p, a, b, ans = 0;
  7.  
  8. int Find(int x) {
  9. int root = x;
  10.  
  11. while (tree[root] >= 0)
  12. root = tree[root];
  13.  
  14. while (root != x && x > 0) {
  15. int temp = tree[x];
  16. tree[x] = root;
  17. x = temp;
  18. }
  19.  
  20. return root;
  21. }
  22.  
  23. int Union(int a, int b) {
  24. int temp = tree[a] + tree[b];
  25.  
  26. if (tree[a] > tree[b]) {
  27. tree[a] = b;
  28. tree[b] = temp;
  29. } else {
  30. tree[b] = a;
  31. tree[a] = temp;
  32. }
  33. }
  34.  
  35. int main() {
  36. cin >> n >> m;
  37.  
  38. for (int i = 0; i < maxn; i++)
  39. tree[i] = -1;
  40.  
  41. for (int i = 0; i < m; i++) {
  42. cin >> p >> a >> b;
  43.  
  44. if (p) {
  45. enemy[a][b] = 1;
  46. enemy[b][a] = 1;
  47. } else {
  48. if (Find(a) != Find(b))
  49. Union(a, b);
  50. }
  51. }
  52.  
  53. for(int i = 1; i <= n; i++) {
  54. int first = 0;
  55. for(int l = 1; l <= n; l++){
  56. if (enemy[i][l] == 1) {
  57. if (first == 0) {
  58. first = l;
  59. continue;
  60. } else {
  61. if (Find(first) != Find(l))
  62. Union(first, l);
  63. }
  64. }
  65. }
  66.  
  67. }
  68.  
  69. for (int i = 1; i <= n; i++)
  70. if (tree[i] <= 0)
  71. ans++;
  72.  
  73. cout << ans << endl;
  74.  
  75. return 0;
  76. }
Add Comment
Please, Sign In to add comment