fork(1) download
copy 
  1. #include<iostream>
  2. #include<fstream>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<climits>
  7. #include<algorithm>
  8. #include<vector>
  9. #include<map>
  10. #include<queue>
  11. #include<stack>
  12. #include<set>
  13. #include<list>
  14.  
  15. using namespace std;
  16.  
  17. #define lli long long int
  18. #define mod 1000000007
  19. #define p push
  20. #define pb push_back
  21. #define mp make_pair
  22.  
  23. vector<lli> g[100007];
  24. bool visited[100007];
  25. vector<lli> a;
  26.  
  27. lli dfs(int index)
  28. {
  29. 	if(visited[index])
  30. 		return 0;
  31.  
  32. 	visited[index]=1;
  33.  
  34. 	vector<lli>::iterator it;
  35. 	lli ans=1;
  36.  
  37. 	for(it=g[index].begin(); it!=g[index].end(); it++)
  38. 		ans+=dfs(*it);
  39.  
  40. 	return ans;
  41. }
  42.  
  43. int main()
  44. 	{
  45. 		lli n, k, i, u, v;
  46. 		lli num, ans;
  47. 		vector<lli>::iterator it;
  48.  
  49. 		cin >> n >> k;
  50.  
  51. 		ans=n*(n-1)/2;
  52.  
  53. 		while(k--)
  54. 			{
  55. 				cin >> u >> v;
  56. 				g[u].pb(v);
  57. 				g[v].pb(u);
  58. 			}
  59.  
  60. 		for(i=1; i<=n; i++)
  61. 			if(!visited[i])
  62. 				{
  63. 					num=dfs(i);
  64. 					a.pb(num);
  65. 				}
  66.  
  67. 		for(it=a.begin(); it!=a.end(); it++)
  68. 			{
  69. 				num=*it;
  70. 				num=num*(num-1);
  71. 				num/=2;
  72. 				ans-=num;
  73. 			}
  74.  
  75. 		cout << ans << endl;
  76. 		return 0;
  77. 	}
Runtime error #stdin #stdout 0s 4736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8RIeJa
language:
C++14 (gcc 8.3)
created:
7 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!