SHARE
TWEET

Untitled

a guest Jul 23rd, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <map>
  6. #include <set>
  7.  
  8. using namespace std;
  9.  
  10. int MAXN = 200001;
  11. int n, m;
  12. int cur_color = 1;
  13. int t;
  14. vector<vector<pair<int, int>>> g(MAXN);
  15. vector<bool> used(MAXN);
  16. vector<int> ans;
  17. vector<int> color(MAXN);
  18. vector<int> tin(MAXN);
  19. vector<int> up(MAXN);
  20.  
  21. void fillgraph();
  22.  
  23. void points_search();
  24.  
  25. void dfs_points(int v, int p);
  26.  
  27. void fillgraph() {
  28.     t = 0;
  29.     cin >> n >> m;
  30.     for (int i = 0; i < n; i++) {
  31.         used[i] = false;
  32.     }
  33.     for (int i = 0; i < m; i++) {
  34.         int a, b;
  35.         cin >> a >> b;
  36.         a--;
  37.         b--;
  38.         bool flag = false;
  39.         if (!flag) {
  40.             g[b].emplace_back(a, i);
  41.             g[a].emplace_back(b, i);
  42.         }
  43.     }
  44. }
  45.  
  46. void points_search() {
  47.     for (int i = 0; i < n; i++) {
  48.         if (!used[i]) {
  49.             dfs_points(i, -1);
  50.         }
  51.     }
  52. }
  53.  
  54. void dfs_points(int v, int p) {
  55.     used[v] = true;
  56.     tin[v] = t;
  57.     up[v] = t;
  58.     t++;
  59.     int ch = 0;
  60.     for (int i = 0; i < g[v].size(); i++) {
  61.         int to = g[v][i].first;
  62.         if (to != p) {
  63.             if (!used[to]) {
  64.                 dfs_points(to, v);
  65.                 up[v] = min(up[v], up[to]);
  66.                 if (up[to] >= tin[v]) {
  67.                     if (p >= 0) {
  68.                         ans.push_back(v);
  69.                     }
  70.                     ch++;
  71.                 }
  72.             } else {
  73.                 up[v] = min(up[v], tin[to]);
  74.             }
  75.         }
  76.     }
  77.     if (p == -1) {
  78.         if (ch > 1) {
  79.             ans.push_back(v);
  80.         }
  81.     }
  82. }
  83.  
  84. void vert(int v, int col, int p) {
  85.     {
  86.         int i = v;
  87.         used[v] = true;
  88.         for (int j = 0; j < g[i].size(); j++) {
  89.             int to = g[v][j].first;
  90.             if (used[to] == false) {
  91.                 if (tin[v] <= up[to]) {
  92.                     int cur = ++cur_color;
  93.                     color[g[v][j].second] = cur;
  94.                     vert(to, cur, v);
  95.                 } else {
  96.                     color[g[v][j].second] = col;
  97.                     vert(to, col, v);
  98.                 }
  99.             } else if (tin[v] > tin[to]) {
  100.                 color[g[v][j].second] = col;
  101.             }
  102.         }
  103.     }
  104. }
  105.  
  106. void comp_vert() {
  107.     for (int i = 0; i < n; i++) {
  108.         if (used[i] == false) {
  109.             cur_color++;
  110.             vert(i, cur_color, -1);
  111.         }
  112.     }
  113. }
  114.  
  115. int main() {
  116.     fillgraph();
  117.     for (int i = 0; i < n; i++) {
  118.         used[i] = false;
  119.     }
  120.     points_search();
  121.     for (int i = 0; i < n; i++) {
  122.         used[i] = false;
  123.     }
  124.     comp_vert();
  125.     set<int> different;
  126.     for (int i = 0; i < m; i++) {
  127.         different.insert(color[i]);
  128.     }
  129.     cout << different.size() << '\n';
  130.     vector<int> answer;
  131.     map<int, int> colorMap;
  132.     int index = 1;
  133.     for (auto el : different) {
  134.         colorMap[el] = index;
  135.         index++;
  136.     }
  137.     for (int i = 0; i < m; i++) {
  138.         answer.push_back((*colorMap.find(color[i])).second);
  139.     }
  140.     for (int i = 0; i < answer.size(); i++) {
  141.         cout << answer[i] << " ";
  142.     }
  143.     cout << '\n';
  144.     return 0;
  145. }
  146. close
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