Cod sursa(job #2965943)

Utilizator andreibazavanAndrei Bazavan andreibazavan Data 16 ianuarie 2023 16:38:06
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

vector <int> G[100005];
typedef pair<int, int> muchie;
stack <muchie> st;
vector < vector<int>> rez;
int n,m,x,y;
bool bif[100005];
int lvl[100005], nma[100005];
void comp_bi(int x, int y)
{
    int tx, ty;
    vector <int> bx;
    do
    {
        tx = st.top().first, ty = st.top().second;
        bx.push_back(tx); bx.push_back(ty);
        st.pop();
    }while(tx!=x || ty!=y);
    rez.push_back(bx);
}
void DFS(int nod, int fth, int hgh)
{
    bif[nod]=1;
    lvl[nod]=nma[nod]=hgh;
    for(int i=0;i<G[nod].size();++i)
    {
        if(!bif[G[nod][i]])
        {
            st.push(muchie(nod, G[nod][i]));
            DFS(G[nod][i], nod, hgh+1);
            nma[nod]=min(nma[nod], nma[G[nod][i]]);
            if(nma[G[nod][i]]>=lvl[nod])comp_bi(nod, G[nod][i]);
        }
        else if(G[nod][i]!=fth)nma[nod]=min(nma[nod], lvl[G[nod][i]]);
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DFS(1,0,1);
    fout<<rez.size()<<'\n';
    for(int i=0;i<rez.size();++i)
    {
        sort(rez[i].begin(), rez[i].end());
        fout<<rez[i][0]<<' ';
        for(int j=1;j<rez[i].size();++j)
            if(rez[i][j]!=rez[i][j-1])fout<<rez[i][j]<<' ';
        fout<<'\n';
    }
    //cout << "Hello world!" << endl;
    return 0;
}