Cod sursa(job #602022)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 8 iulie 2011 19:19:40
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;
int nr;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> G[NMAX];
int lev[NMAX],minlev[NMAX];
stack <pair<int,int> > S;
vector <vector <int> > SOL;
int n,m;
void Read()
{int i,x,y;
fin>>n>>m;
for(i=1;i<=m;i++)
    {
    fin>>x>>y;
    G[x].push_back(y);
    G[y].push_back(x);
   }
}
void comp(int x,int y)
{
	vector <int> :: iterator it;
int tx,ty;
vector<int> con;
do{
tx=S.top().first;ty=S.top().second;
S.pop();
con.push_back(tx);
con.push_back(ty);
}while(!S.empty () and ((x!=tx) or (y!=ty)));

SOL.push_back(con);
}
void DFS(int nod,int tt,int level)
{
vector <int> :: iterator it;
lev[nod]=level;minlev[nod]=level;
for(it=G[nod].begin();it!=G[nod].end();it++)
    {
    if(*it==tt) continue;
    if(!lev[*it])
       {
       S.push(make_pair(nod,*it) );
       DFS(*it,nod,level+1);
       minlev[nod]=min(minlev[nod],minlev[*it]);
       if(minlev[*it]>=lev[nod])
            comp(nod,*it);
       }
    else
      minlev[nod]=min(minlev[nod],lev[*it]);
    }
}
void Write()
{
unsigned int i,j;
fout<<SOL.size()<<"\n";
for (i=0; i<SOL.size(); i++)
{
sort(SOL[i].begin(), SOL[i].end());
SOL[i].erase(unique(SOL[i].begin(), SOL[i].end()), SOL[i].end());
for(j=0;j<SOL[i].size();j++)
   fout<<SOL[i][j]<<" ";
fout<<"\n";
}
}
int main()
{
    Read();
    DFS(1,0,1);
    Write();
    return 0;
}