Cod sursa(job #3303135)

Utilizator andrei.nNemtisor Andrei andrei.n Data 14 iulie 2025 11:11:11
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
template<typename A,typename B>ostream&operator<<
(ostream &out,const pair<A,B>&x){return cout<<x.
first<<' '<<x.second;}void debug(const char*str){
cout<<str;}template<typename T,typename...Args>
void debug(const char*str,T x,Args...args){while(
*str!='\0'){if(*str=='%'){cout<<x;debug(str+1,args
...);return;}else cout<<*str;++str;}}
#else
#define debug
#endif

vector<int> v[100005];
stack<pair<int,int>> st;
bitset<100005> bit;
int depth[100005], up[100005];
vector<vector<int>> comp;

void build(int a, int b)
{
    debug("% %\n", a, b);
    comp.push_back(vector<int>());
    while(!st.empty())
    {
        comp.back().push_back(st.top().first);
        comp.back().push_back(st.top().second);
        if(st.top() == make_pair(a, b))
        {
            st.pop();
            break;
        }
        st.pop();
    }
    sort(comp.back().begin(), comp.back().end());
    comp.back().erase(unique(comp.back().begin(), comp.back().end()), comp.back().end());
}

void dfs(int node)
{
    bit[node] = 1;
    up[node] = depth[node];
    for(const auto &i : v[node])
    {
        if(depth[i] == depth[node] - 1)
            continue;
        if(bit[i])
            up[node] = min(up[node], depth[i]);
        else
        {
            st.emplace(node, i);
            depth[i] = depth[node] + 1;
            dfs(i);
            up[node] = min(up[node], up[i]);
            if(up[i] >= depth[node])
                build(node, i);
        }
    }
}

signed main()
{
    ifstream fin ("biconex.in");
    ofstream fout ("biconex.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    int n, m; fin>>n>>m;
    for(int i=0; i<m; ++i)
    {
        int a, b; fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    depth[1] = 2;
    dfs(1);
    fout<<comp.size()<<'\n';
    for(auto &i : comp)
    {
        for(auto &j : i)
            fout<<j<<' ';
        fout<<'\n';
    }
    return 0;
}