fork download
copy 
  1. #include <cstdio>
  2. #include <map>
  3. #include <vector>
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. const int MAXN = 110000;
  8. vector<int> g[MAXN];
  9. bool used[MAXN];
  10. int timer, tin[MAXN], fup[MAXN];
  11.  
  12. typedef long long ll;
  13.  
  14. map< pair<int,int>, bool > isB;
  15.  
  16. #define mp make_pair
  17. int k = 0;
  18. void IS_BRIDGE( int v, int to ){
  19. 	k++;
  20. 	isB[ mp(v,to) ] = true;
  21. 	isB[ mp(to,v) ] = true;
  22. }
  23.  
  24. void dfs (int v, int p = -1) {
  25. 	used[v] = true;
  26. 	tin[v] = fup[v] = timer++;
  27. 	for (size_t i=0; i<g[v].size(); ++i) {
  28. 		int to = g[v][i];
  29. 		if (to == p)  continue;
  30. 		if (used[to])
  31. 			fup[v] = min (fup[v], tin[to]);
  32. 		else {
  33. 			dfs (to, v);
  34. 			fup[v] = min (fup[v], fup[to]);
  35. 			if (fup[to] > tin[v])
  36. 				IS_BRIDGE(v,to);
  37. 		}
  38. 	}
  39. }
  40.  
  41. int n;
  42.  
  43. void find_bridges() {
  44. 	timer = 0;
  45. 	for (int i=0; i<n; ++i)
  46. 		used[i] = false;
  47. 	for (int i=0; i<n; ++i)
  48. 		if (!used[i])
  49. 			dfs (i);
  50. }
  51. long long res = 0;
  52. int conComps = 0;
  53.  
  54. bool was2 [MAXN];
  55. bool was1 [MAXN];
  56. int dfs2( int v ){
  57. 	was2[v] = true;
  58. 	int sz = g[v].size();
  59.  
  60. 	int res = 1;
  61.  
  62. 	for( int i = 0; i < sz; i++ ){
  63. 		int to = g[v][i];
  64. 		if( !was2[to] )
  65. 			res += dfs2(to);
  66. 	}
  67. 	return res;
  68. }
  69.  
  70. int compCnt [MAXN];
  71. int dfs1(int v){
  72. 	was1[v] = true;
  73. 	int sz = g[v].size();
  74. 	long long q = 0;
  75. 	int cnt = 1;
  76. 	for( int i = 0; i < sz; i++ ){
  77. 		int to = g[v][i];
  78. 		if( !was1[to] ){
  79. 			q = dfs1(to);
  80. 			if( isB[ mp(v,to) ] ){
  81. 				res += ll(q)*(n-q)-1;
  82. 			}
  83. 			cnt+=q;
  84. 		}
  85. 	}
  86. 	return cnt;
  87. }
  88.  
  89. int main(){
  90. 	int m;
  91. 	cin>>n>>m;	
  92. 	int fr,to;
  93. 	for( int i = 0; i < m; i++ ){
  94. 		scanf("%d%d", &fr, &to);
  95. 		fr--,to--;
  96. 		g[fr].push_back(to);
  97. 		g[to].push_back(fr);
  98. 	}
  99. 	for( int i = 0; i < n; i++ ){
  100. 		if( !was2[i] ){
  101. 			compCnt[ conComps++ ] = dfs2(i);
  102.  
  103. 		}
  104. 	}
  105. 	find_bridges();
  106. 	if( conComps>2 ){
  107. 		cout<<0;
  108. 		return 0;
  109. 	}
  110. 	else if( conComps==2 ){
  111. 		cout<< ( ll(m-k)*compCnt[0]*compCnt[1] );
  112. 	}
  113. 	else{
  114.  
  115.  
  116. 		dfs1(0);
  117. 		res += ll(m-k)*( ll(n)*(n-1)/2 - m );
  118. 		cout<<res;
  119. 	}
  120. 	return 0;
  121. }
Success #stdin #stdout 0.02s 5632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1156105936227374224
https://ideone.com/7h9Pt
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!