Cod sursa(job #2077808)

Utilizator smashsmash everything smash Data 28 noiembrie 2017 17:22:39
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream  cin ("biconex.in");
ofstream cout ("biconex.out");

vector <int> graf[100100],sol[100100];
struct bla
{
    int a,b;
} muchii[100001];

int st[100001],vf,n,m,level[100001],hang[100001],l[100001],nr,k;

void read ()
{ int x,y;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        graf[x].push_back(y); l[x]++;
        graf[y].push_back(x); l[y]++;
    }
}
void dfs ()
{
    vf=1; hang[1]=1;
    st[vf]=1; level[1]=1;
    while(vf)
    {
        int nod=st[vf],fiu,ok=0;
        while(l[nod]>0)
        {
            l[nod]--; fiu=graf[nod][l[nod]];
            if(level[fiu]!=0) hang[nod]=min(hang[nod],level[fiu]);
            else {st[++vf]=fiu,muchii[++k].a=nod,muchii[k].b=fiu,hang[fiu]=level[nod],level[fiu]=level[nod]+1;ok=1;break;}
        }
        if(ok==0)
        {
            if(hang[st[vf]]>=level[st[vf-1]] && vf!=1)
            {
                int nod=st[vf-1],fiu=st[vf]; nr++;
                while(muchii[k].a!=nod || muchii[k].b!=fiu) sol[nr].push_back(muchii[k].b),k--;
                sol[nr].push_back(muchii[k].a); sol[nr].push_back(muchii[k].b); k--; vf--;
            } else vf--,hang[st[vf]]=min(hang[st[vf]],hang[st[vf+1]]);

        }
    }
}
void write ()
{
    cout<<nr<<"\n";
    for(int i=1;i<=nr;++i)
    {
        for(int j=0;j<sol[i].size();j++)
            cout<<sol[i][j]<<" ";
        cout<<"\n";
    }
}
int main()
{
    read();
    dfs();
    write();
    cin.close();
    cout.close();
    return 0;
}