fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty