• API
• FAQ
• Tools
• Archive
SHARE
TWEET

a guest Aug 25th, 2019 36 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
2. #include <bits/stdc++.h>
3. #include <cstdio>
4. #include <cstring>
5. #include <cmath>
6. #include <cstring>
7. #include <chrono>
8. #include <complex>
9. #define endl "\n"
10. #define ll long long int
11. #define vi vector<int>
12. #define vll vector<ll>
13. #define vvi vector < vi >
14. #define pii pair<int,int>
15. #define pll pair<long long, long long>
16. #define mod 1000000007
17. #define inf 1000000000000000001;
18. #define all(c) c.begin(),c.end()
19. #define mp(x,y) make_pair(x,y)
20. #define mem(a,val) memset(a,val,sizeof(a))
21. #define eb emplace_back
22. #define f first
23. #define s second
24. using namespace std;
25.
26.
27. // Disjoint Set DataStructure
28. map< ll,ll > parent;        // reserve space for map if n > 10000
29. map< ll,ll > urank;
30. void create(ll x)
31. {
32.     parent[x] = x;
33.     urank[x] = 1;       // rank = no. of nodes in its subtree
34. }
35. ll find(ll x)
36. {
37.     if( parent[x] != x )    //path compression
38.     {
39.         parent[x] = find(parent[x]) ;
40.     }
41.     return parent[x];
42. }
43. void merge(ll x, ll y)
44. {
45.     ll xroot = find(x);
46.     ll yroot = find(y);
47.     if( urank[xroot] <= urank[yroot] )  // Union by rank
48.     {
49.         parent[xroot] = yroot ;
50.         urank[yroot] = urank[yroot] + urank[xroot] ;
51.     }
52.     else
53.     {
54.         parent[yroot] = xroot;
55.         urank[xroot] = urank[xroot] + urank[yroot] ;
56.     }
57. }
58.
59.
60. int main()
61. {
62.     int T;
63.     cin>>T;
64.     for(int t=1;t<=T;t++)
65.     {
66.
67.         int n,m;
68.
69.         cin>>n>>m;
70.
71.         for(int i=0; i<n; i++) create(i);
72.
73.         int black=0,red=0;
74.
75.         for(int i=0; i<m; i++){
76.             int u,v;
77.             cin>>u>>v;
78.
79.             if(find(u-1)!=find(v-1)){
80.                 ++black;
81.                 merge(u-1,v-1);
82.             }
83.         }
84.
85.         for(int i=0; i<n; i++){
86.             if(find(i)==i) red++;
87.         }
88.
89.         ll ans = black+(red-1)*2;
90.         cout<<"Case #"<<t<<": "<<ans<<endl;
91.     }
92.     return 0;
93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top