Cod sursa(job #2801993)

Utilizator Andrei012Trache Andrei Andrei012 Data 17 noiembrie 2021 12:26:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>

using namespace std;
#define mp make_pair

ifstream in("biconex.in");
ofstream out("biconex.out");

set<int> ans1;
vector<int> v[100001];
stack<pair<int,int> > st;
vector<pair<int,int> > cbi[100001];

int depth[100001],parc[100001],ans;

int dfs(int node)
{
    parc[node]=1;
    int up=(1<<30);
    for(auto i : v[node])
    {
        st.push(make_pair(node,i));

        if(parc[i]==1)
        {
            if(depth[node]<=depth[i])
                st.pop();
            up=min(up,depth[i]);
            continue;
        }
        else
        {
            depth[i]=depth[node]+1;
            int nodeant=dfs(i);
            up=min(up,nodeant);
            if(nodeant>=depth[node])
            {
                ++ans;
                while(st.size() && st.top() != mp(node,i))
                {
                    cbi[ans].push_back(st.top());
                    st.pop();
                }
                cbi[ans].push_back(st.top());
                st.pop();
            }
        }
    }
    return up;

}


int main()
{
    int n,m,i,x,y;
    in>>n>>m;
    for(i=1; i<=m; ++i)
    {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    out<<ans<<'\n';
    for(i=1; i<=ans; ++i)
    {
        for(auto j : cbi[i])
        {
            if(ans1.find(j.first) == ans1.end())
                ans1.insert(j.first);
            if(ans1.find(j.second) == ans1.end())
                ans1.insert(j.second);
        }
        for(auto j : ans1)
            out<<j<<" ";
        out<<'\n';
        ans1.clear();
    }
    return 0;
}