Cod sursa(job #2921031)

Utilizator RaresPoinaruPoinaru-Rares-Aurel RaresPoinaru Data 26 august 2022 22:09:06
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");

const int MAXN=200010;

int n,m,visit[MAXN],timp,r,timpl[MAXN],timph[MAXN];
int rez;
vector <int> g[MAXN],c[MAXN];
stack <pair <int, int>> st;

void solve (int nod, int prevn){
    if (visit[nod]==1)
        return;
    st.push({prevn,nod});
    visit[nod]=1;
    timpl[nod]=timph[nod]=timp;
    timp++;
    for (int i=0;i<g[nod].size ();++i){
        int nextn=g[nod][i];
        if (nextn==prevn) continue;
        if (visit[nextn]==0){
            solve (nextn,nod);
            timpl[nod]=min (timpl[nod],timpl[nextn]);
            if (timph[nod]<=timpl[nextn]){
                ++rez;
                while (st.top ().first!=nod or st.top ().second!=nextn){
                    c[rez].push_back (st.top().first);
                    c[rez].push_back (st.top ().second);
                    st.pop ();
                }
                c[rez].push_back (st.top().first);
                c[rez].push_back (st.top ().second);
                st.pop ();
            }
        }
        else
            timpl[nod]=min (timpl[nod],timph[nextn]);

    }
}

int main()
{
    fin >>n>>m;
    for (int i=1;i<=m;++i){
        int x,y;
        fin >>x>>y;
        g[x].push_back (y);
        g[y].push_back (x);
    }
    for (int i=1;i<=n;++i){
        if (visit[i]==0){
            r=i;
            solve (i,0);
            while (st.empty ()==false)
                st.pop ();
        }
    }
    fout <<rez<<'\n';
    for (int i=1;i<=rez;++i){
        sort (c[i].begin (),c[i].end ());
        fout <<c[i][0]<<' ';
        for (int j=1;j<c[i].size ();++j){
            if (c[i][j]!=c[i][j-1])
                fout <<c[i][j]<<' ';
        }
        fout <<'\n';
    }
    fin.close ();
    fout.close ();
    return 0;
}