SHARE
TWEET

Untitled

lalalalalalalaalalla Sep 18th, 2019 (edited) 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <iomanip>
  5. #include <queue>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <tuple>
  9. #include <iomanip>
  10. #include <stdio.h>
  11. #include <numeric>
  12. #include <map>
  13. #include <bitset>
  14. #include <set>
  15. #include <stack>
  16. #include <queue>
  17.  
  18. //#pragma GCC optimize("Ofast,no-stack-protector")
  19. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  20. //#pragma GCC optimize("unroll-loops")
  21. //#pragma GCC optimize("fast-math")
  22. //#pragma GCC optimize("section-anchors")
  23. //#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
  24. //#pragma GCC optimize("vpt")
  25. //#pragma GCC optimize("rename-registers")
  26. //#pragma GCC optimize("move-loop-invariants")
  27. //#pragma GCC optimize("unswitch-loops")
  28. //#pragma GCC optimize("function-sections")
  29. //#pragma GCC optimize("data-sections")
  30. //#pragma GCC optimize("branch-target-load-optimize")
  31. //#pragma GCC optimize("branch-target-load-optimize2")
  32. //#pragma GCC optimize("btr-bb-exclusive")
  33.  
  34. #define int long long
  35. #define ll long long
  36. #define ull unsigned long long
  37. #define all(a) a.begin(), a.end()
  38. #define pii pair<int, int>
  39. #define pb push_back
  40. #define ld long double
  41.  
  42. using namespace std;
  43.  
  44. const int INF = 1e13;
  45. //const int mod = 2600000069;
  46. //const int p = 179;
  47.  
  48. int n, m;
  49. vector<vector<pii>> g;
  50. vector<vector<int>> ng;
  51. vector<bool> ban, used;
  52. vector<pii> br;
  53. vector<int> tin, dp;
  54. int timer = 0;
  55. vector<int> colors;
  56.  
  57. void dfs(int v, int p = -1) {
  58.     used[v] = 1;
  59.     tin[v] = dp[v] = timer++;
  60.     for (auto u: g[v]) {
  61.         if (u.first == p) continue;
  62.         if (used[u.first]) {
  63.             dp[v] = min(dp[v], tin[u.first]);
  64.         } else {
  65.             dfs(u.first, v);
  66.             dp[v] = min(dp[v], dp[u.first]);
  67.             if (dp[u.first] > tin[v]) {
  68.                 br.pb({min(u.first, v), max(u.first, v)});
  69.                 ban[u.second] = 1;
  70.             }
  71.         }
  72.     }
  73. }
  74.  
  75. vector<int> comp_size;
  76.  
  77. void mark(int v, int color) {
  78.     used[v] = 1;
  79.     colors[v] = color;
  80.     for (auto u: g[v]) {
  81.         if (ban[u.second] || used[u.first]) continue;
  82.         mark(u.first, color);
  83.     }
  84. }
  85.  
  86. const int mod = 1000000007;
  87.  
  88. signed main() {
  89.     ios_base::sync_with_stdio(0);
  90.     cin.tie(0);
  91.     cout.tie(0);
  92. //    freopen("input.in", "r", stdin);
  93. //    freopen("output.out", "w", stdout);
  94.     cin >> n >> m;
  95.     g.resize(n);
  96.     ban.assign(m, 0);
  97.     tin.resize(n);
  98.     dp.assign(n, INF);
  99.     used.assign(n, 0);
  100.     colors.resize(n);
  101.     int a, b;
  102.     for (int i = 0; i < m; i++) {
  103.         cin >> a >> b;
  104.         a--;b--;
  105.         g[a].pb({b, i});
  106.         g[b].pb({a, i});
  107.     }
  108.     for (int i = 0; i < n; i++) {
  109.         if (!used[i]) dfs(i, -1);
  110.     }
  111.     used.assign(n, 0);
  112.     int comp = 0;
  113.     for (int i = 0; i < n; i++) {
  114.         if (!used[i]) {
  115.             mark(i, comp);
  116.             comp++;
  117.         }
  118.     }
  119.     comp_size.assign(comp, 0);
  120.     for (auto k: colors) {
  121.         comp_size[k]++;
  122.     }
  123.     ng.resize(comp);
  124.     for (auto k: br) {
  125.         if (colors[k.first] != colors[k.second]) {
  126.             ng[k.first].pb(k.second);
  127.             ng[k.second].pb(k.first);
  128.         }
  129.     }
  130.     int ans2 = 1, ans1 = 0;
  131.     for (int i = 0; i < comp; i++) {
  132.         if (ng[i].size() == 1) {
  133.             ans1++;
  134.             ans2 *= comp_size[i];
  135.             ans2 %= mod;
  136.         } else if (ng[i].size() == 0) ans1++;
  137.     }
  138.     cout << ans1 << " " << ans2;
  139. }
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