daily pastebin goal
66%
SHARE
TWEET

Untitled

raliev May 29th, 2012 1,176 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <set>
  7. #include <assert.h>
  8.  
  9. using namespace std;
  10.  
  11. int n, m;
  12. int times = 0;
  13. int colors = 0;
  14. int bridges = 0;
  15.  
  16. vector< vector<int> > g;
  17. vector<int> enter, ret, cnt;
  18. vector<int> size;
  19. vector<bool> used;
  20. vector<int> color;
  21.  
  22.  
  23. long long ans = 0;
  24.  
  25. void dfs(int v)
  26. {
  27.         size[v] = 1;
  28.         for (size_t i = 0; i < g[v].size(); i++)
  29.         {
  30.                 int u = g[v][i];
  31.                 if (size[u] == 0)
  32.                 {
  33.                         dfs(u);
  34.                         size[v] += size[u];
  35.                 }
  36.         }
  37. }
  38.  
  39. void paint(int v, int col)
  40. {
  41.         used[v] = true;
  42.         color[v] = col;
  43.         for (size_t i = 0; i < g[v].size(); i++)
  44.         {
  45.                 int u = g[v][i];
  46.                 if (!used[u])
  47.                         paint(u, col);
  48.         }
  49. }
  50.  
  51. void search_bridge(int v, int p = -1)
  52. {
  53.         used[v] = true;
  54.         enter[v] = ret[v] = times++;
  55.         for (size_t i = 0; i < g[v].size(); i++)
  56.         {
  57.                 int t = g[v][i];
  58.                 if (t == p) continue;
  59.                 if (used[t])
  60.                         ret[v] = min(ret[v], enter[t]);
  61.                 else
  62.                 {
  63.                         search_bridge(t, v);
  64.                         ret[v] = min(ret[v], ret[t]);
  65.                         if (ret[t] > enter[v])
  66.                         {
  67.                                 bridges++;
  68.                                 cnt.push_back(size[t]);
  69.                         }
  70.                 }
  71.         }
  72. };
  73.  
  74. int main()
  75. {
  76.         // freopen("edges.in", "r", stdin);
  77.         // freopen("edges.out", "w", stdout);
  78.         cin >> n >> m;
  79.         assert(1 <= n && n <= 1e5);
  80.         assert(0 <= m && m <= 2e5);
  81.         g.resize(n);
  82.         int x, y;
  83.     set< pair<int, int> > q;
  84.         for (int i = 0; i < m; i++)
  85.         {
  86.                 cin >> x >> y;
  87.             assert(1 <= x && x <= n);
  88.                 assert(1 <= y && y <= n);
  89.                 assert(x != y);
  90.         pair<int, int> e = make_pair(min(x, y), max(x, y));
  91.         assert(q.count(e) == 0);
  92.         q.insert(e);
  93.         g[x - 1].push_back(y - 1);
  94.                 g[y - 1].push_back(x - 1);
  95.         }
  96.     q.clear();
  97.         used.resize(n, false);
  98.         color.resize(n);
  99.         size.resize(n);
  100.         for (size_t i = 0; i < n; i++)
  101.                 if (!used[i])
  102.                 {
  103.                         paint(i, colors++);
  104.                         dfs(i);        
  105.                 }
  106.         if (colors > 2)
  107.         {
  108.                 cout << "0\n";
  109.                 return 0;
  110.         }
  111.         enter.resize(n, 0);
  112.         ret.resize(n, 0);
  113.         used.assign(n, false);
  114.         for (size_t i = 0; i < n; i++)
  115.                 if (!used[i]) search_bridge(i);
  116.         if (colors == 2)
  117.         {
  118.                 long long size1 = 0;
  119.                 long long size2 = 0;
  120.                 for (size_t i = 0; i < n; i++)
  121.                         if (color[i] == 1) size1++;
  122.                         else size2++;
  123.                 ans = size1 * size2;
  124.                 ans *= (m - bridges);
  125.                 cout << ans << endl;
  126.                 return 0;
  127.         }
  128.         if (colors == 1)
  129.         {
  130.                 ans =  m - bridges;
  131.                 ans *= (long long)n * (long long)(n - 1) / 2 - m;
  132.         for (size_t i = 0; i < cnt.size(); i++)
  133.                         ans += (long long)(n - cnt[i]) * cnt[i] - 1;
  134.                 cout << ans << endl;
  135.                 return 0;
  136.         }
  137. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top