Cod sursa(job #955505)

Utilizator misinozzz zzz misino Data 31 mai 2013 21:56:00
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<fstream>
#include<vector>
#include<stack>
#define pb push_back
#define mp make_pair
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int nr,i,x,y,n,m,xx,yy,j,pr[100100],viz[100100];
vector<int>l[100100];
stack<pair<int,int> >st;
vector<vector<int> >sol;
void dfs(int x,int tata)
{
    int nou;
    ++nr;
    viz[x]=nr;
    pr[x]=nr;
    for(vector<int>::iterator it=l[x].begin();it!=l[x].end();++it)
    if(*it!=tata)
    {
        if(viz[*it])
        {
            pr[x]=min(pr[x],pr[*it]);
            continue;
        }
        nou=*it;
        st.push(mp(x,nou));
        dfs(nou,x);
        pr[x]=min(pr[nou],pr[x]);
        if(pr[nou]>=viz[x])
        {
            sol.pb(vector<int>());
            do{
                xx=st.top().first;
                yy=st.top().second;
                st.pop();
                sol.back().pb(yy);
            }while(xx!=x&&yy!=nou);
            sol.back().pb(x);
        }

    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        l[x].pb(y);
        l[y].pb(x);
    }
    for(i=1;i<=n;++i)
    if(!viz[i])
    dfs(i,0);
    g<<sol.size()<<'\n';
    for(i=0;i<sol.size();++i)
    {
        for(j=0;j<sol[i].size();++j)
        g<<sol[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}