fork download 
  1. /*
  2. PAIRING PROBLEM:
  3.  
  4.  
  5. tried using DSU ==> 
  6. ex:	7 5						0			4
  7. 	0 1					  1				  5
  8. 	1 2					2   3				6	
  9. 	1 3		
  10. 	4 5
  11. 	5 6
  12. 											   indexes:	0 1 2 3  4 5 6
  13. i have made "parents[]" such that its output will be =[-4 0 0 0 -3 4 4]
  14.  
  15. indexes are nodes and value on them are as follows:
  16. 1)-ve number=super_parent
  17. 2)-ve number ka magnitude means total components in that component
  18. 3)+ve number means position of superparent 
  19.  
  20.  
  21. FOR Calculating final answer
  22.  
  23. {
  24. 		component1	|	component2	|	component3				 . . . .  . . .   component_Nth
  25. 			0		|		4		|		7
  26.   		1			|		  5		|	  		8				.  . . .  .  .
  27. 	2		3		|			6	|	
  28. == 	4nodes here		|	3nodes here	|		2nodes here			  . . . . . . .    Cn nodes here
  29. }
  30. components[3]=[4,3,2, . . . . Cn];
  31.  
  32. answer = every possible combination taking 2 elements at a time from components array;
  33.  
  34. answer = (a1+a2+a3. . . .+an)^2 - ((a1)^2+(a2)^2. . . .(an)^2)
  35. ======> this equation give every combination . . . . .
  36. answer = answer/2, becoz combination repeat hongai 2 baar
  37.  
  38.  
  39. I DID IT LIKE THIS STILL GETTING WRONG_ANS, 
  40.  
  41. code bhi check kiya pata ni kya galti hai. . . . . .logic thik thak mazboot lagra hai...
  42.  
  43. [[code aur logic mazboot lagre hai isliye DOUBT pucha]]
  44.  
  45. */
  46. #include<iostream>
  47. #include<vector>
  48. using namespace std;
  49. const int mod_wala=1e9+7;
  50. const int max_size=1e5+1;
  51. vector<int> parents(max_size,-1);
  52. int superparent(int x){
  53. 	return parents[x]<0?x:superparent(parents[x]); 
  54. }
  55. int main() {
  56. 	int n,m;
  57. 	long long int ans1=0,ans2=0;
  58. 	cin>>n>>m;
  59. 	while(m--){
  60. 		int x,y;
  61. 		cin>>x>>y;
  62. 		if(superparent(x)!=superparent(y)){
  63. 			if(parents[superparent(x)]<=parents[superparent(y)]){
  64. 				parents[y]=superparent(x);
  65. 				parents[superparent(x)]--;
  66. 			}else{
  67. 				swap(x,y);
  68. 				parents[y]=superparent(x);
  69. 				parents[superparent(x)]--;
  70. 			}
  71. 		}
  72. 	}
  73. 	for(int i=0;i<n;i++){
  74. 		// cout<<parents[i]<<" ";
  75. 		if(parents[i]<0){
  76. 			ans2+=parents[i];
  77. 			ans1+=parents[i]*parents[i];
  78. 			// cout<<parents[i]<<" ";
  79. 		}
  80. 	}
  81. 	cout<<(ans2*ans2-ans1)/2<<"\n";
  82. 	return 0;
  83. }
Runtime error #stdin #stdout 0s 4404KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Gciw2v
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!