Cod sursa(job #1028824)

Utilizator a96tudorAvram Tudor a96tudor Data 14 noiembrie 2013 18:37:49
Problema Componente biconexe Scor 94
Compilator cpp Status done
Runda Arhiva educationala Marime 2.46 kb
#include<cstdio>
#include<list>
#include<vector>
#include<utility>
#include<stack>

#define f first
#define s second
#define N_MAX 100010
#define M_MAX 200010
#define pb push_back
using namespace std;

stack < pair <int,int> > Q;
vector <int> G[N_MAX];
vector < vector <int> > sol;
vector<int> cop;

bool fol[N_MAX];
int niv[N_MAX],low[N_MAX],T[N_MAX],Val[N_MAX];
int N,nr;


inline void Insert(int x,int niv)
{
    if (Val[x]==niv) return;
    Val[x]=niv;
    cop.pb(x);
}

//parcurgere DF

inline void DF(int x,int n)
{
    int y=0,a,b;
    vector <int> :: iterator it;

    niv[x]=n;
    low[x]=n;
    for (it=G[x].begin();it!=G[x].end();++it)
        if (!fol[*it])
            {
                fol[*it]=true;
                T[*it]=x;
                Q.push(make_pair(x,*it));
                DF(*it,n+1);
                y=*it;
                nr++;
                if (low[x]>low[y]) low[x]=low[y];
                if (low[y]>=niv[x])
                    {
                        //X E PCT DE ARTICULATIE =>AM GASIT O COMPONENTA BICONEXA

                        int a,b;
                        cop.clear();
                        do
                            {
                                a=Q.top().f;
                                b=Q.top().s;
                                Q.pop();
                                Insert(a,nr);
                                Insert(b,nr);
                            }
                        while (a!=x && b!=T[x]);
                        sol.pb(cop);
                    }
            }
            else
                {
                    y=*it;
                    if (y!=T[x] && low[x]>niv[y])
                        low[x]=niv[y];
                }
}

//citire

inline void Load_Data()
{
    int M,i,x,y;
    scanf("%d%d",&N,&M);
    for (i=1;i<=M;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].pb(y);
        G[y].pb(x);
    }

    for (i=1;i<=N;i++)
        fol[i]=false;
}

inline void Write_Data()
{
    int i,j;
    printf("%d",sol.size());
    for (i=0;i<sol.size();++i)
    {
        printf("\n");
        for (j=0;j<sol[i].size();++j)
            printf("%d ",sol[i][j]);
    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    Load_Data();
    for (int i=1;i<=N;i++)
        if (!fol[i]) DF(i,1);
    Write_Data();
    fclose(stdin);
    fclose(stdout);
    return 0;
}