Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <map>
- #include <set>
- using namespace std;
- int MAXN = 200001;
- int n, m;
- int cur_color = 1;
- int t;
- vector<vector<pair<int, int>>> g(MAXN);
- vector<bool> used(MAXN);
- vector<int> ans;
- vector<int> color(MAXN);
- vector<int> tin(MAXN);
- vector<int> up(MAXN);
- void fillgraph();
- void points_search();
- void dfs_points(int v, int p);
- void fillgraph() {
- t = 0;
- cin >> n >> m;
- for (int i = 0; i < n; i++) {
- used[i] = false;
- }
- for (int i = 0; i < m; i++) {
- int a, b;
- cin >> a >> b;
- a--;
- b--;
- // if (a > b) {
- // std::swap(a, b);
- // }
- bool flag = false;
- // for (int j = 0; j < g[a].size(); j++) {
- // if (g[a][j] == b) {
- // flag = true;
- // }
- // }
- // for (int j = 0; j < g[b].size(); j++) {
- // if (g[b][j] == a) {
- // flag = true;
- // }
- // }
- if (!flag) {
- g[b].emplace_back(a, i);
- g[a].emplace_back(b, i);
- }
- }
- }
- void points_search() {
- for (int i = 0; i < n; i++) {
- if (!used[i]) {
- dfs_points(i, -1);
- }
- }
- }
- void dfs_points(int v, int p) {
- used[v] = true;
- tin[v] = t;
- up[v] = t;
- t++;
- int ch = 0;
- for (int i = 0; i < g[v].size(); i++) {
- int to = g[v][i].first;
- if (to != p) {
- if (!used[to]) {
- dfs_points(to, v);
- up[v] = min(up[v], up[to]);
- if (up[to] >= tin[v]) {
- if (p >= 0) {
- ans.push_back(v);
- }
- ch++;
- }
- } else {
- up[v] = min(up[v], tin[to]);
- }
- }
- }
- if (p == -1) {
- if (ch > 1) {
- ans.push_back(v);
- }
- }
- }
- void vert(int v, int col, int p) {
- {
- int i = v;
- used[v] = true;
- for (int j = 0; j < g[i].size(); j++) {
- int to = g[v][j].first;
- if (p != to) {
- if (used[to] == false) {
- if (tin[v] <= up[to]) {
- int cur = ++cur_color;
- color[g[v][j].second] = cur;
- vert(to, cur, v);
- } else {
- color[g[v][j].second] = col;
- vert(to, col, v);
- }
- } else if (tin[v] > tin[to]) {
- color[g[v][j].second] = col;
- }
- }
- }
- }
- }
- void comp_vert() {
- for (int i = 0; i < n; i++) {
- if (used[i] == false) {
- cur_color++;
- vert(i, cur_color, -1);
- }
- }
- }
- int main() {
- fillgraph();
- for (int i = 0; i < n; i++) {
- used[i] = false;
- }
- points_search();
- for (int i = 0; i < n; i++) {
- used[i] = false;
- }
- comp_vert();
- set<int> different;
- for (int i = 0; i < m; i++) {
- different.insert(color[i]);
- }
- cout << different.size() << '\n';
- vector<int> answer;
- map<int, int> colorMap;
- int index = 1;
- for (auto el : different) {
- colorMap[el] = index;
- index++;
- }
- for (int i = 0; i < m; i++) {
- answer.push_back((*colorMap.find(color[i])).second);
- }
- for (int i = 0; i < answer.size(); i++) {
- cout << answer[i] << " ";
- }
- cout << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement