Cod sursa(job #2404623)

Utilizator nicholascantarNicholas David Cantar Gogitidze nicholascantar Data 13 aprilie 2019 10:19:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.16 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> v[100005];
vector < pair<int,int> > st;
vector <int> ans[100001];
int q[100005],niv[100005],low[100005],sol[100005],t[100005],rad,nr,ans2,ans1,n,m,i,x,y,ansnr,j,nr2;
void df(int k) {
    int i,x;
    low[k]=niv[k];
    for (i=0;i<v[k].size();i++) {
        x=v[k][i];
        if (!niv[x]) {
            niv[x]=niv[k]+1;
            t[x]=k;
            df(x);
            low[k]=min(low[k],low[x]);
            if (low[x]>=niv[k]) nr++;
        }
        else if (x!=t[k]) low[k]=min(low[k],niv[x]);
    }
}

void df2(int k) {
    int i,x,a1,a2,j;
    low[k]=niv[k];
    for (i=0;i<v[k].size();i++) {
        x=v[k][i];
        if (x!=t[k] && niv[x]<niv[k]) st.push_back({x,k});
        if (!niv[x]) {
            niv[x]=niv[k]+1;
            t[x]=k;
            df2(x);
            low[k]=min(low[k],low[x]);
            if (low[x]>=niv[k]) {
                nr2=0;
                do {
                    a1=st[st.size()-1].first;
                    a2=st[st.size()-1].second;
                    sol[++nr2]=a1;
                    sol[++nr2]=a2;
                    st.pop_back();
                } while (!st.empty() && !(a1==x && a2==k || a1==k && a2==x));
                sort(sol+1,sol+nr2+1);
                for (j=1;j<=nr2;j++)
                    if (sol[j]!=sol[j-1]) g<<sol[j]<<" ";
                g<<'\n';
            }
        }
        else if (x!=t[k]) low[k]=min(low[k],niv[x]);
    }
}

void init() {
    int i;
    for (i=1;i<=n;i++)
        niv[i]=low[i]=t[i]=0;
}
int main()
{
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1; i<=n; i++)
    {
        if(niv[i]==0)
        {
            niv[i]=1;
            nr=0;
            rad=i;

            q[ans1]=i;
            df(i);

            if(nr>1){sol[i]=1;}
            else sol[i]=0;
        }
    }
    niv[1]=1;
    df(1);
    g<<nr<<'\n';
    init();
    niv[1]=1;
    df2(1);
    return 0;
}