Cod sursa(job #2111278)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 21 ianuarie 2018 19:59:00
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 4.61 kb
/*#include<bits/stdc++.h>
#define mod 666013
using namespace std;

int N;

vector <int> T[mod];

//imi definesc functia hash ca fiind h[x]=x%mod
//valorile sinonime le plasez intr-o lista inlantuita. In vectorul T pe poz i voi retine un pointer catre inceputul listei inlantuite formate din taote valorile x pentru care h[x]=i

vector<int>::iterator caut(int x)
{
    int h=x%mod;
    vector<int>:: iterator it;
    for(it=T[h].begin();it!=T[h].end();it++)
        if(*it==x) return it;
    return T[h].end();
}

inline void add(int x)
{
    int h=x%mod;
    vector<int>::iterator it=caut(x);
    if(it==T[h].end())
        T[h].push_back(x);
}


inline void sterg(int x)
{
    int h=x%mod;
    vector<int>::iterator it=caut(x);
    if(it!=T[h].end())
        T[h].erase(it);
}


void read_solve()
{
    int op,val;
    freopen("hashuri.in","r",stdin);
    freopen("hashuri.out","w",stdout);
     for(scanf("%d",&N);N;N--)
     {
         scanf("%d %d",&op,&val);
         if(op==1)
         {
             add(val);
             continue;
         }
         if(op==2)
         {
             sterg(val);
             continue;
         }
         printf("%d\n", caut(val)!=T[val%mod].end());
     }
}

int main()
{
    read_solve();
}*/

//rabin-karp
/*#include<bits/stdc++.h>
#define N 2000001
using namespace std;

char T[N],P[N];
int n,m,nrv;
int st[N],vf;

unsigned long putere(int d,int m)
{
    int i;
    unsigned long p=1;
    for(i=1;i<m;i++) p*=d;
    return p;
}

bool check(char *P,char *T, int k)
{
    int i;
    for(i=0;i<m;i++)
        if(P[i]!=T[k+i]) return 0;
    return 1;
}


void rabin_karp(char *T, char *P, int d, int q,int q1)
{
    int i,k;
    unsigned long h,p=0,t0=0,t1=0,p1=0;
    n=strlen(T);
    m=strlen(P);
    h=putere(d,m)%q;
    for(i=0;i<m;i++)
    {
        p=(d*p+P[i])%q;
        t0=(d*t0+T[i])%q;

        p1=(d*p1+P[i])%q1;
        t1=(d*t1+T[i])%q1;
    }


    for(k=0;k<=n-m;k++)
    {
        if(p1==t1 && p==t0)
            if(check(P,T,k))
            {nrv++;
                    st[++vf]=k;
                  }
        t0=(t0+d*q-T[k]*h)%q;
        t0=(t0*d+T[k+m])%q;

        t1=(t1+d*q1-T[k]*h)%q1;
        t1=(t1*d+T[k+m])%q1;
    }

}



int main()
{
    int i,x=-1;
    freopen("strmatch.in","r",stdin);
    scanf("%s \n %s", P, T);
    rabin_karp(T,P,73,100007,100021);
    freopen("strmatch.out","w",stdout);
    cout<<nrv<<endl;
    for(i=1;i<=vf;++i)
        cout<<st[i]<<' ';

}*/

//componente biconexe
#include<bits/stdc++.h>
#define N 100000
using namespace std;

int n, num, vf,nrfii,nr,start=1;
vector<int> G[N];

int dfn[N],low[N];
bool Art[N];

struct Muchie{int f,t;};
vector <int> sol[N];
Muchie S[N];

void read()
{
    FILE * fin=fopen("biconex.in","r");
    int x,y,m,i;
    fscanf(fin,"%d %d",&n,&m);
    for(i=0;i<m;i++)
    {
        fscanf(fin,"%d %d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void init()
{
    for(int i=1;i<=n;i++)
        dfn[i]=low[i]=-1;
    vf=0;
    S[0].f=start;
    S[0].t=-1;
}

void afisare(int x, int u)
{
    bool viz[N];
    memset(viz,0,sizeof(viz));
    Muchie p=S[vf];
    nr++;
    do
    {
        p=S[vf--];
        if(!viz[p.f]){sol[nr].push_back(p.f);
        viz[p.f]=1;
        }
        if(!viz[p.t])
        {
            sol[nr].push_back(p.t);
            viz[p.t]=1;
        }

    }
    while(p.t!=u || p.f!=x);
}


void Biconex(int u,int tu)
{
    int x,p;
    dfn[u]=++num;
    low[u]=dfn[u];
    vector<int>::iterator it;
    for(it=G[u].begin();it!=G[u].end();it++)
    {
        if(*it!=tu && dfn[*it]<dfn[u])
        {
            S[++vf].f=*it;
            S[vf].t=u;
        }

        if(dfn[*it]==-1)
        {
            if(u==start) nrfii++;
            Biconex(*it,u);
            low[u]=min(low[u],low[*it]);
            if(low[*it]>=dfn[u]) //u este punct de articulatie
            {
                if(u!=start) Art[u]=1;
                afisare(*it,u);
            }


        }

        else
            if(*it!=tu) //*it a mai fost vizitat, deci [u,*it] e muchie de intoarcere
            low[u]=min(low[u],dfn[*it]);
    }
}

int main()
{
    int i,j;
    read();
    init();
    Biconex(start,-1);
    if(nrfii>=2) Art[start]=1;
    freopen("biconex.out","w",stdout);
    cout<<nr<<endl;
    for(i=1;i<=nr;i++)
    {
        sort(sol[i].begin(),sol[i].end());
        for(j=0;j<sol[i].size();j++)
            cout<<sol[i][j]<<' ';
        cout<<endl;
    }


}