Cod sursa(job #2540689)

Utilizator st_marianStoica Marian st_marian Data 7 februarie 2020 15:11:09
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <bits/stdc++.h>

#define NMAX 100005
#define cin fin
#define cout fout
#define pb push_back

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

int n, m;
int sol;
vector<int> mat[NMAX];
vector<int> G[NMAX];
int used[NMAX], L[NMAX], nv[NMAX], t[NMAX];
vector< pair<int, int> > st;

void read();
void DFS(int nod);
void processing(int tata, int nod);
int main()
{
    read();

    for(int i=1; i<=n; ++i)
    {
        if(used[i]) continue;
        nv[i]=1;
        used[i]=1;
        DFS(i);
    }

    cout<<sol<<'\n';
    for(int i=0; i<sol; ++i)
    {
        for(auto it:mat[i])
            cout<<it<<' ';
        cout<<'\n';
    }
    return 0;
}
void processing(int tata, int nod)
{
    set<int> s;

    while(true)
    {
        s.insert(st.back().first);
        s.insert(st.back().second);

        if(st.back().first==tata && st.back().second==nod)
        {
            st.pop_back();
            break;
        }
        st.pop_back();
    }

    for(auto it:s)
        mat[sol].pb(it);

    ++sol;
}
void DFS(int nod)
{
    L[nod]=nv[nod];

    for(auto it:G[nod])
    {
        if(it!=t[nod] && nv[it]<nv[nod] && nv[it])
            st.pb(make_pair(nod, it));
        if(!used[it])
        {
            used[it]=1; nv[it]=nv[nod]+1;   t[it]=nod;
            st.pb(make_pair(nod, it));

            DFS(it);

            if(L[it]<L[nod])
                L[nod]=L[it];
            if(L[it]>=nv[nod])
                processing(nod, it);
        }
        else if(it!=t[nod] && L[nod]>nv[it])
            L[nod]=nv[it];
    }
}
void read()
{
    cin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x, y;
        cin>>x>>y;
        G[x].pb(y);
        G[y].pb(x);
    }
}