Cod sursa(job #2123513)

Utilizator cicero23catalin viorel cicero23 Data 6 februarie 2018 12:32:00
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define f first
#define s second
#define mp make_pair
#define N 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> v[N];
stack <pair<int,int> > st;
vector <int> rez[N];
pair<int,int> aux;
int viz[N],t[N],niv[N],low[N],sol[N],r,nr,cont;
void DF(int x)
{
    int i;
    viz[x]=1;
    low[x]=niv[x];
    for(i=0; i<v[x].size(); i++)
    {
        if(v[x][i]!=t[x]&&niv[x]>niv[v[x][i]])
        {
            st.push(mp(x,v[x][i]));
            if(!viz[v[x][i]])
            {
                niv[v[x][i]]=niv[x]+1;
                t[v[x][i]]=x;
                DF(v[x][i]);
                low[x]=min(low[x],low[v[x][i]]);
                if(low[v[x][i]]>=niv[x])
                {
                    cont++;
                    do
                    {
                        aux=st.top();
                        rez[cont].push_back(aux.f);
                        rez[cont].push_back(aux.s);
                        st.pop();
                    }while((aux.f!=x||aux.s!=v[x][i])&&(aux.s!=x||aux.f!=v[x][i]));

                }
            }
            else if(v[x][i]!=t[x])
            {
                low[x]=min(low[x],niv[v[x][i]]);
            }
        }
    }
}
int main()
{
    int n,m,i,x,y,j;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    viz[1]=1;
    niv[1]=1;
    DF(1);
    g<<cont<<'\n';
    for(i=1;i<=cont;i++)
    {
        sort(rez[i].begin(),rez[i].end());
    }
    for(i=1;i<=cont;i++)
    {
        g<<rez[i][0]<<" ";
        for(j=1;j<rez[i].size();j++)
        if(rez[i][j]!=rez[i][j-1])g<<rez[i][j]<<" ";
        g<<'\n';
    }
    return 0;
}