Cod sursa(job #2811696)

Utilizator Matei_PanzariuMatei Panzariu Matei_Panzariu Data 2 decembrie 2021 21:50:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 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 tx,ty;
    do
    {
        ty=st.top().second;
        tx=st.top().first;
        ra[cnt].push_back(ty);
        ra[cnt].push_back(tx);
        // cout<<tx<<' '<<ty<<'\n';
        st.pop();
    }
    while(ty!=y || tx!=x);
    //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++)
    {
        int x=-1;
        sort(ra[i].begin(),ra[i].end());
        for(int j=0; j<ra[i].size(); j++)
            if(ra[i][j]!=x)
            {
                x=ra[i][j];
                cout<<ra[i][j]<<' ';
            }
        cout<<'\n';
    }
}