Cod sursa(job #2077770)

Utilizator smashsmash everything smash Data 28 noiembrie 2017 16:49:39
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <vector>

using namespace std;

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

vector <int> graf[100100],sol[100100];

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

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,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)
            { ++nr; sol[nr].push_back(st[vf-1]);
                for(int u=vf;st[u]!=0;u++)
                    sol[nr].push_back(st[u]),st[u]=0;
                 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;
}