Задача D. Компоненты вершинной двусвязности

#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;

vector <int> tin;
vector <int> up;
vector <bool> was;
vector <vector<int>> gr;
vector <bool> cut_p;
int P = 0;
vector <bool> root;
vector <bool> connected;
void dfs(int v, int last, int timer) {
    was[v] = true;
    tin[v] = up[v] = timer;

    int child = 0;
    for (int u : gr[v]) {

        if (u == last) {

            continue;
        }
        else if (was[u] == true) {

            up[v] = min(up[v], tin[u]);
        }
        else if (was[u] == false) {
            dfs(u, v, timer + 1);
            up[v] = min(up[v], up[u]);
            if (up[u] >= tin[v] && v != last) {
                if (!cut_p[v]) P++;
                cut_p[v] = true;
            }
            child++;
        }
    }
    if (v == last && child > 1) {
        if (!cut_p[v]) P++;
        cut_p[v] = true;
        root[v] = true;
    }

}

bool cp(int v, int u) {//check that (v) is cut_point
    if (up[u] >= tin[v]) {
        return true;
    }
    else {
        return false;
    }
}


int max_col = 0;
int cnt;
map < pair<int, int>, int> marker;
void mark(int v, int last, int color, int cnt) {
    //cout << "V in = " << v + 1 << '\n';
    was[v] = true;
    for (int u : gr[v]) {
        //cout << "(" << v + 1 << "," << u + 1 << ")" << '\n';
        if (u == last) {
            //cout << "skip\n";
            continue;
        }
        else if (!was[u]) {
            if (cut_p[v] && cp(v, u)) {
                //cout << "ONE\n";
                if (!(root[v] && cnt == 0)) {
                    max_col++;
                }
                cnt++;
                marker[{min(u, v), max(u, v)}] = max_col;
                //cout << "marker[{min(u, v), max(u, v)}] = " << marker[{min(u, v), max(u, v)}] << '\n';
                //cout << "max_col = " << max_col << '\n';
                mark(u, v, max_col, cnt);
            }
            else {
                //cout << "TWO\n";
                marker[{min(u, v), max(u, v)}] = color;
                //cout << "color = " << color << '\n';
                mark(u, v, color, cnt);
            }
        }
        else if (was[u] && tin[v] > tin[u]) {
            //cout << "(" << v + 1 << "," << u + 1 << ")" << '\n';
            //cout << "THREE\n";
            //cout << "color = " << color << '\n';
            marker[{min(u, v), max(u, v)}] = color;
        }
    }
}


int main()
{
    int n, m;
    cin >> n >> m;
    gr.resize(n);
    cut_p.resize(n, false);
    connected.resize(n, false);
    vector <pair <int, int> > Edges;
    root.resize(n, false);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        gr[a].push_back(b);
        gr[b].push_back(a);
        connected[a] = true;
        connected[b] = true;
        Edges.push_back({ min(a,b), max(a,b) });
        marker[{ min(a, b), max(a, b) }] = -999;
    }
    tin.resize(n, -4);
    up.resize(n, 1e9);
    was.resize(n, false);
    for (int i = 0; i < n; ++i) {
        if (was[i] || !connected[i]) continue;
        dfs(i, i, 0);
    }
    /*cout << "\ntin\n";
    for (int i = 0;i<n;++i){
        cout<<i+1<<": "<<tin[i]<<'\n';
    }cout<<'\n';
    cout<<"up\n";
    for (int i=0;i<n;++i){
        cout<<i+1<<": "<<up[i]<<'\n';
    }cout<<'\n';
    cout <<"amount of cut_points = "<< P<< '\n';
    cout << "points:\n";
    for (int i= 0;i<n;++i){
        if (cut_p[i]){
            cout<<i+1<<'\n';
        }
    }*/
    //cout << "ROOT = " << root << '\n';
    was.assign(n, false);
    //cout << "GO MARKING\n";
    for (int i = 0; i < n; ++i) {
        if (was[i] || !connected[i]) continue;
        max_col++;
        //cout << "i = " << i << "  max_col = " << max_col << '\n';
        cnt = 0;
        mark(i, i, max_col, cnt);
    }
    //cout<<"num of components = "<<max_col<<'\n';
    //cout << "\marker\n";
    cout << max_col << '\n';
    for (auto x : Edges) {
        //cout<<"("<<x.first+1<<","<<x.second+1<<")="<<marker[x]<<'\n';
        cout << marker[x] << ' ';
    }
}
/*
5 5
1 2
1 3
3 4
2 4
5 4
*/
/*
3 2
1 2
1 3
*/
/*
4 3
1 2
1 3
1 4
*/