Cod sursa(job #2811685)

Utilizator Matei_PanzariuMatei Panzariu Matei_Panzariu Data 2 decembrie 2021 21:10:04
Problema Componente biconexe Scor 64
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
vector<vector<int> >mu,ra;
vector<int>c;
stack<pair<int,int>>st;
int n,m,low[100002],f[100002],cnt;
void remake(int x,int y)
{
    //cout<<'\n';
    cnt++;
    ra.push_back(c);
    int ty=st.top().second;
    int tx=st.top().first;
    ra[cnt].push_back(st.top().second);
    ra[cnt].push_back(st.top().first);
    while(ty!=y || tx!=x)
    {
       // cout<<tx<<' '<<ty<<'\n';
        st.pop();
        tx=st.top().first;
        ty=st.top().second;
        ra[cnt].push_back(st.top().first);
    }
    //cout<<tx<<' '<<ty<<'\n';
    st.pop();
}
void DF(int x,int nr,int nod)
{
    //cout<<x<<'\n';
    low[x]=f[x]=nr;
    for(int i=0;i<mu[x].size();i++)
    {
        if(f[mu[x][i]]==0)
        {
            st.push(make_pair(x,mu[x][i]));
            DF(mu[x][i],nr+1,x);
            low[x]=min(low[x],low[mu[x][i]]);
            if(low[mu[x][i]]>=f[x])
                remake(x,mu[x][i]);
        }
        else
            low[x]=min(low[x],f[mu[x][i]]);
    }
    //cout<<x<<'\n';
}
int main()
{
    cin>>n>>m;
    ra.push_back(c);
    mu.resize(n+1);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        mu[x].push_back(y);
        mu[y].push_back(x);
    }
    DF(1,1,0);
    cout<<cnt<<'\n';
    for(int i=1;i<=cnt;i++)
    {
        sort(ra[i].begin(),ra[i].end());
        for(int j=0;j<ra[i].size();j++)
            cout<<ra[i][j]<<' ';
        cout<<'\n';
    }
}