Cod sursa(job #2174561)

Utilizator zhm248Mustatea Radu zhm248 Data 16 martie 2018 12:34:48
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
vector<int>g[100001],cc[100001];
int discover[100001],low[100001],nivel,t[100001],sol;
struct muchie
{
    int x,y;
};

stack<muchie>st;
void dfs(int nod)
{
    nivel++;
    discover[nod]=low[nod]=nivel;
    for(int i=0;i<g[nod].size();++i)
    {
        int fiu=g[nod][i];
        if(fiu!=t[nod])
        {
            if(!discover[fiu])
            {
                muchie c;
                c.x=nod;
                c.y=fiu;
                st.push(c);
                t[fiu]=nod;
                dfs(fiu);
                if(low[fiu]>=discover[nod])
                {
                    int x,y;
                    sol++;
                    do
                    {
                        x=st.top().x,y=st.top().y;
                        st.pop();
                        cc[sol].push_back(y);
                    }while(x!=nod&&y!=fiu);
                    cc[sol].push_back(nod);
                }
                low[nod]=min(low[nod],low[fiu]);
            }
            low[nod]=min(low[nod],discover[fiu]);
        }
    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int n,m,i,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(i=1;i<=n;++i)
    {
        if(!discover[i])
            dfs(i);
    }
    printf("%d\n",sol);
    for(i=1;i<=sol;++i)
    {
        for(int j=0;j<cc[i].size();++j)
        {
            printf("%d ",cc[i][j]);
        }
        printf("\n");
    }
    return 0;
}