Cod sursa(job #1033225)

Utilizator a96tudorAvram Tudor a96tudor Data 16 noiembrie 2013 16:51:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.48 kb
#include<cstdio>
#include<vector>
#include<utility>
#include<stack>
#include<algorithm>
#include<cmath>

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

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

bool pus[N_MAX];
int T[N_MAX],low[N_MAX],niv[N_MAX],a[N_MAX];
int N,NR;

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

inline void DF(int x,int n)
{
    vector <int> :: iterator it;
    int y;
    low[x]=n;
    niv[x]=n;
    pus[x]=true;
    for (it=G[x].begin();it!=G[x].end();++it)
    {
        y=*it;
        if (!pus[y])
            {
                pus[y]=true;
                T[y]=x;
                Q.push(make_pair(x,y));

                DF(y,n+1);
                NR++;
                low[x]=min(low[x],low[y]);
                if (low[y]>=niv[x])
                    {
                        //AM GASIT PCT DE ART => AVEM COMPONENTA BICONEXA
                        cop.clear();
                        int a,b;
                        do
                            {
                                a=Q.top().f;
                                b=Q.top().s;
                                Q.pop();
                                ins(a,NR);
                                ins(b,NR);
                            }
                        while (a!=x && b!=T[x]);
                        Sol.pb(cop);
                    }
            }
            else
                        {
                            if (y!=T[x]) low[x]=min(low[x],niv[y]);
                        }

    }

}

inline void Load_Data()
{
    int i,x,y,M;
    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++)
        pus[i]=false;
}

inline void Write_Data()
{
    int i;
    vector <int> :: iterator it;
    printf("%d\n",Sol.size());
    for (i=0;i<Sol.size();++i)
    {
        for (it=Sol[i].begin();it!=Sol[i].end();++it)
            printf("%d ",*it);
        printf("\n");
    }
    return;
}

int main()
{
    int i;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    Load_Data();
    for (i=1;i<=N;i++)
        if (!pus[i])
            {
                DF(i,1);
            }
    Write_Data();
    fclose(stdin);
    fclose(stdout);
    return 0;
}