fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define crap ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  4. typedef long long int ll;
  5. typedef unsigned long long ull;
  6. typedef std::vector<int> vi;
  7. typedef std::vector<ll> vll;
  8. typedef std::vector<vi > vvi;
  9. typedef std::vector<vll > vvll;
  10. typedef std::pair<int,int> ii;
  11. typedef std::pair< ll, ll > lp;
  12. typedef std::vector<lp> vii;
  13. typedef std::vector<vii > vvii;
  14.  
  15. #define pb push_back 
  16. #define PB pop_back
  17. #define pf push_front
  18. #define PF pop_front
  19. #define mp make_pair
  20. #define mem(a,b) memset(a,b,sizeof(a))
  21. #define in(a,n) F(i,0,n-1)cin>>a[i]
  22. #define in1(a,n) F(i,1,n)cin>>a[i]
  23. #define ff first
  24. #define ss second
  25. #define F(i,a,b) for (ll i=a;i<=b;i++)
  26. #define RF(i,a,b) for(ll i=a;i>=b;i--)
  27. #define rep(i,n) F(i,0,n-1)
  28. #define clr(a) (a).clear()
  29. #define rz resize
  30. #define sqr(a) ((a) * (a))
  31. #define sz(a) int((a).size())
  32. #define all(a) (a).begin(), (a).end()
  33. #define rall(a) (a).rbegin(),
  34.  
  35. vi g[500005];
  36. int vis[500005];
  37. int dis[500005];
  38. int low[500005];
  39. vii bridge;
  40. int tim;
  41.  
  42. void dfs(int v,int vp)
  43. {
  44. 	vis[v]=1;
  45. 	dis[v]=low[v]=tim++;
  46.  
  47. 	for (int u : g[v])
  48. 	{
  49. 		if (u==vp)continue;
  50.  
  51. 		if (vis[u])
  52. 			low[v]=min(low[v],dis[u]);
  53.  
  54. 		else
  55. 		{
  56. 			dfs(u,v);
  57.  
  58. 			low[v]=min(low[v],low[u]);
  59.  
  60. 			if (low[u] > dis[v])
  61. 				bridge.pb({u,v});
  62. 		}
  63. 	}
  64. }
  65.  
  66. int main(int argc, char const *argv[])
  67. {
  68. 	crap;
  69. 	int n,m,u,v;
  70. 	cin>>n>>m;
  71. 	rep(i,m)
  72. 	{
  73. 		cin>>u>>v;
  74. 		g[u].pb(v);
  75. 		g[v].pb(u);
  76. 	}
  77. 	//time=0;
  78. 	dfs(1,0);
  79.  
  80. 	set<int> idk;
  81. 	for (auto i : bridge)
  82. 	{
  83. 		idk.insert(min(i.ff,i.ss));
  84. 	}
  85. 	ll x=ll(sz(idk));
  86. 	ll num=x*(n-1);
  87. 	num-=(x*(x-1))/2;
  88. 	ll den=(ll(n))*(n-1);
  89. 	den/=2;
  90.  
  91. 	double final=(1.0*num)/den;
  92.  
  93. 	cout<<fixed<<setprecision(5)<<final<<"\n";
  94.  
  95. 	return 0;
  96. }
Runtime error #stdin #stdout 0s 32816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nRTTHz
problem GRAFFDEF, based on SPOJ submission 22497005 (CPP14), 2018-10-13 09:18:46
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!