fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define FORE(i, a, b) for(int i = a; i <= b; i++)
  3. #define FORD(i, a, b) for(int i = a; i >= b; i--)
  4. #define FOR(i, a, b) for(int i = a; i < b; i++)
  5. const int MAXN = 1e5 * 5;
  6. const int INF = 1e9 + 7;
  7.  
  8. using namespace std;
  9.  
  10. int n, m;
  11. bool a[50][50];
  12. typedef pair<int, int> ii;
  13. vector< ii > s1, s2;
  14. int dem;
  15. bool Free[50];
  16.  
  17. inline void duyet(int u)
  18. {
  19.     //cout<<u<<endl;
  20.     dem++;
  21.     Free[u] = 0;
  22.     FORE(v, 1, n) if (u != v && a[u][v] && Free[v] > 0){
  23.         duyet(v);
  24.     }
  25. }
  26.  
  27. vector< int > adj[MAXN];
  28. int Low[MAXN], Num[MAXN], Count = 0, Pa[MAXN], C[MAXN];
  29.  
  30. inline void dfs(int u)
  31. {
  32.     Count++;
  33.     Num[u] = Count;
  34.     Low[u] = n + 1;
  35.     C[u] = 1;
  36.     FOR(i, 0, adj[u].size()){
  37.         int v = adj[u][i];
  38.         if (Pa[v] == 0){
  39.             Pa[v] = u;
  40.             dfs(v);
  41.             C[u] += C[v];
  42.             Low[u] = min(Low[u], Low[v]);
  43.         } else
  44.             if (Pa[u] != v) Low[u] = min(Low[u], Num[v]);
  45.     }
  46. }
  47.  
  48. long long sd[3];
  49. int main()
  50. {
  51.     ios::sync_with_stdio(0); cin.tie(0);
  52.     #ifndef ONLINE_JUDGE
  53.     freopen("REFORM.inp", "r", stdin);
  54.     freopen("REFORM.out", "w", stdout);
  55.     #endif //yeulaptrinh.pw
  56.     cin >> n >> m;
  57.  
  58.     if (n <= 20){
  59.         FORE(i, 1, m){
  60.             int x, y;
  61.             cin >> x >> y;
  62.             a[x][y] = 1;
  63.             a[y][x] = 1;
  64.         }
  65.         long long ans = 0;
  66.         FORE(x, 1, n) FORE(y, x + 1, n) if (a[x][y] == 1){
  67.             s2.push_back(ii(x, y));
  68.         } else s1.push_back(ii(x, y));
  69.         FOR(i, 0, s1.size())
  70.         FOR(j, 0, s2.size()){
  71.             int u1 = s1[i].first, v1 = s1[i].second;
  72.             int u2 = s2[j].first, v2 = s2[j].second;
  73.             a[u1][v1] = 1; a[v1][u1] = 1;
  74.             a[u2][v2] = 0; a[v2][u2] = 0;
  75.             memset(Free, 1, sizeof(Free));
  76.             dem = 0;
  77.            // cout<<u1<<" "<<v1<<" "<<u2<<" "<<v2<<endl;
  78.  
  79.             duyet(1);
  80.             if (dem == n) ans++;
  81.             a[u1][v1] = 0; a[v1][u1] = 0;
  82.             a[u2][v2] = 1; a[v2][u2] = 1;
  83.         }
  84.         cout << ans << endl;
  85.     }
  86.     else
  87.  
  88.     {
  89.         int u, v;
  90.         FORE(i, 1, m){
  91.             cin >> u >> v;
  92.             adj[u].push_back(v);
  93.             adj[v].push_back(u);
  94.         }
  95.         int dlt = 0;
  96.         FORE(u, 1, n) if (Pa[u] == 0){
  97.             Pa[u] = -1;
  98.             Count = 0;
  99.             dfs(u);
  100.             dlt++;
  101.             sd[dlt] = Count;
  102.         }
  103.         //cout<<dlt<<"??"<<endl;
  104.         if (dlt > 2){
  105.             cout << 0 << endl;
  106.             return 0;
  107.         }
  108.  
  109.         //FORE(u, 1, n) cout << C[u]<<" ";cout<<endl;
  110.             long long ans = 0, Cau = 0, SZ = 1LL * n * (n - 1) / 2;
  111.             FORE(v, 1, n){
  112.                 u = Pa[v];
  113.                 if (u == -1 || Low[v] < Num[v]) continue;
  114.                 ans += 1LL * C[v] * (n - C[v]) - 1;
  115.                 Cau++;
  116.             }
  117.             //cout << Cau<<"??"<<ans<<endl;
  118.             if (dlt == 1){
  119.                 ans += 1LL * (m - Cau) * (SZ - m);
  120.                 cout << ans;
  121.             } else{
  122.                 long long ans = 1LL * sd[1] * sd[2] * (m - Cau);
  123.                 cout << ans;
  124.             }
  125.  
  126.     }
  127.     return 0;
  128. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.pas:1: no include path in which to find bits/stdc++.h
stdout
copy 
Standard output is empty
https://ideone.com/YP8Bmv
language:
Pascal (gpc 20070904)
created:
6 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!