fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. const int N=1e5+1;
  5. int n, m;
  6. vector<int> adj[N];
  7. vector<int> v[N];
  8. int cnt[N];
  9. bool vis[N];
  10. int t;
  11. int tin[N];
  12. int sz[N];
  13. int par[N];
  14. int siz;
  15. bool bridge;
  16. int cmp;
  17.  
  18. const int MOD=998244353;
  19.  
  20. int add(int a, int b){
  21. 	return (a+b)%MOD;
  22. }
  23.  
  24. void add2(int &a, int b){
  25. 	a+=b;
  26. 	if(a>=MOD) a-=MOD;
  27. }
  28.  
  29. void dfs(int x){
  30. 	vis[x]=1;
  31. 	tin[x]=++t;
  32. 	sz[x]=1;
  33. 	for(int k:adj[x]){
  34. 		if(!vis[k]){
  35. 			dfs(k);
  36. 			sz[x]+=sz[k];
  37. 			par[k]=x;
  38. 			// cout << "par[" << k << "] = " << x << "\n";
  39. 		}
  40. 	}
  41. }
  42.  
  43. int dfs2(int x){
  44. 	int low=1e9;
  45. 	for(int k:adj[x]){
  46. 		if(k==par[x]) continue;
  47. 		if(par[k]==x){
  48. 			low=min(low, dfs2(k));
  49. 		}
  50. 		else low=min(low, tin[k]);
  51. 	}
  52. 	// cout << "dfs2 " << x << " " << low << '\n';
  53. 	if(par[x] && low>=tin[x]){
  54. 		v[siz].push_back(sz[x]);
  55. 		bridge=1;
  56. 		// cout << par[x] << "->" << x << " bridge\n";
  57. 	}
  58. 	return low;
  59. }
  60.  
  61. int main(){
  62. 	cin.tie(0)->sync_with_stdio(0);
  63.  
  64. 	cin >> n >> m;
  65. 	for(int i=0; i<m; i++){
  66. 		int u,v; 
  67. 		cin >> u >> v;
  68. 		adj[u].push_back(v);
  69. 		adj[v].push_back(u);
  70. 	}
  71.  
  72. 	for(int i=1; i<=n; i++){
  73. 		if(vis[i]) continue;
  74. 		dfs(i);
  75. 		cnt[sz[i]]++;
  76. 		siz=sz[i];
  77. 		cmp++;
  78. 		dfs2(i);
  79. 	}
  80.  
  81. 	vector<int> dp(n+1);
  82. 	dp[0]=1;
  83.  
  84. 	for(int i=1; i<=n; i++){
  85. 		if(!cnt[i]) continue;
  86. 		vector<int> ps(n+1);
  87. 		ps[0]=1;
  88. 		for(int j=1; j<=n; j++){
  89. 			ps[j]=add(j-i>=0?ps[j-i]:0, dp[j]);
  90. 		}
  91. 		for(int j=1; j<=n; j++){
  92. 			dp[j]=ps[j]-(j-i*(cnt[i]+1)>=0?ps[j-i*(cnt[i]+1)]:0);
  93. 			if(dp[j]<0) dp[j]+=MOD;
  94. 		}
  95. 	}
  96.  
  97. 	long long ans=-1;
  98.  
  99. 	cnt[0]=1;
  100. 	v[0].push_back(0);
  101. 	for(int i=0; i<=n; i++){
  102. 		if(!cnt[i]) continue;
  103. 		for(int j=n; j>=cnt[i]*i; j--){
  104. 			if(i) dp[j]-=dp[j-cnt[i]*i];
  105. 			if(dp[j]<0) dp[j]+=MOD;
  106. 		}
  107. 		vector<int> pos;
  108. 		for(int j=0; j<=n; j++){
  109. 			if(dp[j]) pos.push_back(j);
  110. 		}
  111. 		int s=v[i].size();
  112. 		for(int j=0; j<s; j++) v[i].push_back(i-v[i][j]);
  113. 		sort(v[i].begin(), v[i].end());
  114. 		v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
  115. 		int j=0;
  116. 		reverse(v[i].begin(), v[i].end());
  117. 		for(int k:v[i]){
  118. 			while(j+1<int(pos.size()) && pos[j+1]+k<=n/2) j++;
  119. 			if(pos[j]+k<=n/2) ans=max(ans, (long long)pos[j]+k);
  120. 		}
  121.  
  122. 		for(int j=cnt[i]*i; j<=n; j++){
  123. 			if(i) dp[j]+=dp[j-cnt[i]*i];
  124. 			if(dp[j]>=MOD) dp[j]-=MOD;
  125. 		}
  126. 	}
  127. 	if(cmp==1 && !bridge) ans=-1;
  128. 	cout << (ans==-1?-1:ans*(ans-1)/2 + ((long long)n-ans)*(n-ans-1)/2 + 1 - m);
  129. }
Success #stdin #stdout 0.01s 8600KB
comments (?)
stdin
copy 
7 5
5 7
2 4
1 3
5 1
5 6
stdout
copy 
5
https://ideone.com/3rP9g7
language:
C++14 (gcc 8.3)
created:
1 year 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!