fork download
copy 
  1. /* CPP Tempelate
  2.  * @author Devashish Tyagi
  3.  */
  4.  
  5. #include <algorithm>
  6. #include <cctype>
  7. #include <cmath>
  8. #include <cstdio>
  9. #include <cstdlib>
  10. #include <cstring>
  11. #include <iostream>
  12. #include <map>
  13. #include <queue>
  14. #include <set>
  15. #include <sstream>
  16. #include <stack>
  17. #include <string>
  18. #include <vector>
  19. #include <list>
  20.  
  21.  
  22. #define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
  23. #define pi pair<int,int>
  24. #define vi vector<int>
  25. #define all(v) v.begin(),v.end()
  26.  
  27. #define PB push_back
  28. #define MP make_pair
  29. #define sz(a) (int)(a).size()
  30.  
  31. #define FOR(i,a,b) for(int (i) = (a); (i) < (b); ++(i))  
  32. #define RFOR(i,a,b) for(int (i) = (a)-1; (i) >= (b); --(i))  
  33. #define CLEAR(a) memset((a),0,sizeof(a))
  34.  
  35. #define INF 100000000
  36. #define PI 2*acos(0.0)
  37.  
  38. using namespace std;
  39. typedef long long ll;
  40.  
  41. string convertInt(int number)
  42. {
  43.    stringstream ss;//create a stringstream
  44.    ss << number;//add number to the stream
  45.    return ss.str();//return a string with the contents of the stream
  46. }
  47.  
  48. int convertString(string s){
  49.     int num;
  50.     stringstream sstr(s); // create a stringstream
  51.     sstr>>num; // push the stream into the num
  52.     return num;
  53. }
  54.  
  55. vector<int> parent(100001,0);
  56. vector<int> rank(100001,0);
  57. int n;
  58.  
  59. void reset(int n){
  60.     FOR(i,0,2*n){
  61.         parent[i] = i;
  62.         rank[i] = 0;
  63.     }
  64. }
  65.  
  66. int find(int v){
  67.     if (parent[v] == v)
  68.         return v; 
  69.     return parent[v] = find(parent[v]);
  70. }
  71.  
  72. bool add(int t, int i, int j){
  73.     if (i>=n || j>= n) return false;
  74.     if (t == 0){
  75.         int ni=i+n, nj=j+n;
  76.         int p1 = find(i), p2 = find(j), p3 = find(ni), p4 = find(nj);
  77.         if (p1 == p4)
  78.             return false;
  79.         else if (p2 == p3)
  80.             return false;
  81.         else if (p1 != p2){
  82.             if (rank[p1] < rank[p2])
  83.                 swap(p1,p2);
  84.             parent[p2] = p1;
  85.             if (rank[p1] == rank[p2])
  86.                 rank[p1]++;
  87.             return true;
  88.         }
  89.         else
  90.             return true;
  91.     }
  92.     else{
  93.         int ni=i+n, nj=j+n;
  94.         int p1 = find(i), p2 = find(j), p3 = find(ni), p4 = find(nj);
  95.         if (p1 == p2)
  96.             return false;
  97.         else if (p1 == p4)
  98.             return false;
  99.         else if (p2 != p3){
  100.             if (rank[p2] < rank[p3])
  101.                 swap(p2,p3);
  102.             parent[p2] = p3;
  103.             if (rank[p2] == rank[p3])
  104.                 rank[p2]++;
  105.             return true;
  106.         }
  107.         else
  108.             return true;
  109.     }
  110. }
  111.  
  112. int main(void){
  113.     int t;
  114.     scanf("%d",&t);
  115.     while(t--){
  116.         int k;
  117.         scanf("%d %d",&n,&k);
  118.         reset(n);
  119.         int ans = 0;
  120.         FOR(i,0,k){
  121.             int t,i,j;
  122.             scanf("%d %d %d",&t,&i,&j); 
  123.             if (!add(t-1,i-1,j-1))
  124.                 ans++;
  125.         }
  126.         printf("%d\n",ans);
  127.     }
  128. }
Success #stdin #stdout 0.01s 2692KB
comments (?)
stdin
copy 
1
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
stdout
copy 
3
https://ideone.com/6W5Na
language:
C++ (gcc 8.3)
created:
12 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!