Cod sursa(job #3037938)

Utilizator pctirziuTirziu Petre pctirziu Data 26 martie 2023 18:07:33
Problema Componente biconexe Scor 76
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.84 kb
#include <fstream>
#include <stack>
#include <set>
#include <vector>

using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int nmax = 1e5 + 5;
vector <int> edge[nmax];
int cate[nmax], disc[nmax], low[nmax], vis[nmax], compnod[nmax], comp[nmax], compmuchii[nmax], parent[nmax];
int id, cnt;
set <int> s[nmax];
stack <pair<int, int>> st;
bool ok = true;
void check(int node)
{
    vis[node] = 1;
    for(int i = 0; i < edge[node].size(); i++)
        if(!vis[edge[node][i]])
            check(edge[node][i]);
}
void dfs(int node)
{
    disc[node] = low[node] = ++cnt;
    int cnt1 = 0;
    for(int i = 0; i < edge[node].size(); i++){
        int child = edge[node][i];
        if(disc[child] == 0){
            cnt1++;
            st.push({node, child});
            parent[child] = node;
            dfs(child);
            low[node] = min(low[child], low[node]);
            if((node == 1 and cnt1 > 1) or (node != 1 and low[child] >= disc[node])){
                id++;
                while(st.top().first != node and st.top().second != child){
                    /*if(comp[st.top().first] != id){
                        cate[st.top().first]++;
                        compnod[id]++;
                        compmuchii[id]++;
                    }
                    if(comp[st.top().second] != id){
                        cate[st.top().second]++;
                        compnod[id]++;
                        compmuchii[id]++;
                    }
                    comp[st.top().first] = id;
                    comp[st.top().second] = id;
                    if(cate[st.top().first] > 2 or cate[st.top().second] > 2)
                        ok = false;*/
                    //cout << st.top().first << " " << st.top().second << "\n";
                    s[id].insert(st.top().first);
                    s[id].insert(st.top().second);
                    st.pop();
                }
                /*if(comp[st.top().first] != id){
                    cate[st.top().first]++;
                    compnod[id]++;
                    compmuchii[id]++;
                }
                if(comp[st.top().second] != id){
                    cate[st.top().second]++;
                    compnod[id]++;
                    compmuchii[id]++;
                }
                comp[st.top().first] = id;
                comp[st.top().second] = id;
                if(cate[st.top().first] > 2 or cate[st.top().second] > 2)
                    ok = false;*/
                //cout << st.top().first << " " << st.top().second << "\n";
                s[id].insert(st.top().first);
                s[id].insert(st.top().second);
                st.pop();
            }
        }
        else if(child != parent[node]){
            low[node] = min(low[node], disc[child]);
            if(disc[node] > disc[child])
                st.push({node, child});
        }
    }
}
int main()
{
    //int t;
    //cin >> t;
    int t = 1;
    while(t--){
        int n, m;
        cin >> n >> m;
        for(int i = 1; i <= m; i++){
            int x, y;
            cin >> x >> y;
            edge[x].push_back(y);
            edge[y].push_back(x);
        }
        check(1);
        for(int i = 1; i <= n; i++)
            if(!vis[i])
                ok = false;
        dfs(1);
        if(!st.empty()){
            id++;
            while(!st.empty()){
                /*if(comp[st.top().first] != id){
                    cate[st.top().first]++;
                    compnod[id]++;
                    compmuchii[id]++;
                }
                if(comp[st.top().second] != id){
                    cate[st.top().second]++;
                    compnod[id]++;
                    compmuchii[id]++;
                }
                comp[st.top().first] = id;
                comp[st.top().second] = id;
                if(cate[st.top().first] > 2 or cate[st.top().second] > 2)
                    ok = false;*/
                //cout << st.top().first << " " << st.top().second << "\n";
                s[id].insert(st.top().first);
                s[id].insert(st.top().second);
                st.pop();
            }
        }
        cout << id << "\n";
        for(int i = 1; i <= id; i++){
            for(auto it = s[i].begin(); it != s[i].end(); it++)
                cout << *(it) << " ";
            cout << "\n";
        }
        /*for(int i = 1; i <= id; i++){
            if(compnod[i] * (compnod[i] - 1) / 2 != compmuchii[i])
                ok = false;
        }
        if(!ok)
            cout << "NU\n";
        else{
            cout << "DA\n";
        }
        for(int i = 1; i <= n; i++){
            disc[i] = low[i] = compnod[i] = compmuchii[i] = parent[i] = cate[i] = comp[i] = vis[i] = 0;
            edge[i].clear();
        }*/
    }
    return 0;
}