Cod sursa(job #1257513)

Utilizator victor_crivatCrivat Victor victor_crivat Data 7 noiembrie 2014 20:46:13
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#include <stack>
#define mp make_pair
#define pb push_back
#define mare 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int>v[mare];
vector<pair<int,int> >q[mare],z;
vector<pair<int,int> > ::iterator it;
bool used[mare],ok[mare];
int x,y,m,n,niv[mare],l[mare],t[mare],rad,nr,i,a,b,lung,nrx=0;

inline void MemComp( int X, int Y )
{
    vector< int > C;
    pair< int, int > Mct, M1 = mp( X, Y ), M2 = mp( Y, X );

    do
    {
        Mct = z.back();
        q[nrx].pb(mp(Mct.first,Mct.second));
        z.pop_back();
    }
    while( Mct != M1 && Mct != M2 );
}
void df(int x)
{vector <int>::iterator it;
used[x]=true;
l[x]=niv[x];
for (it=v[x].begin();it!=v[x].end();it++)
{if(*it!= t[x]&&niv[x]>niv[*it]) z.pb(mp(*it,x));

if(used[*it]==false)
{niv[*it]=niv[x]+1;
t[*it]=x;
df(*it);
if (l[x] > l[*it]) l[x] = l[*it];
        if (l[*it] >= niv[x])
        {nrx++;
        MemComp( *it, x );
        }
}
else if (*it!=t[x]&& l[x]> niv[*it]) l[x] = niv[*it];
}}
int main()
{f>>n>>m;
for (i=1;i<=m;i++)
 {f>>x>>y;
     v[x].push_back(y);
  v[y].push_back(x);
 }
for (i=1;i<=n;i++)
if (!used[i])
{niv[i]=1;
 rad=i;
 nr=0;
 df(i);

}
int j;
g<<nrx<<'\n';
for (i=1;i<=nrx;i++)
{for (j=1;j<=n;j++) ok[j]=false;
    for (it=q[i].begin();it!=q[i].end();it++)
{if (!ok[(*it).first]) {g<<(*it).first<<" ";ok[(*it).first]=true;}
if (!ok[(*it).second]) {g<<(*it).second<<" ";ok[(*it).second]=true;}}
g<<'\n';
}

}