Cod sursa(job #775607)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 8 august 2012 16:21:06
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
/* componente biconexe */

#include<fstream>
#include<cstdio>
#include<cstdlib>
#include<list>
#include<cmath>
#include<stack>
#include<vector>
using namespace std;

const char infile[]="biconex.in";
const char outfile[]="biconex.out";
int n,m,i,j,nrcbc;
list<int> a[200001],q; 
int niv[100001],low[100001];
stack< pair<int,int> > stiva;

vector< vector<int> > bigV;
vector<int> v;

ifstream f(infile);
ofstream g(outfile);

void cbconex(int x, int y)
{v.clear();
pair<int, int> p;
do{
p=stiva.top();
stiva.pop();
v.push_back(p.second);
}while(p.first!=x && p.second!=y);

v.push_back(p.first);
bigV.push_back(v);
nrcbc++;
}

void depth(int x, int father=0)
{list<int>::iterator it; 
 low[x]=niv[x];
 for(it=a[x].begin(); it!=a[x].end(); it++)
   {if(*it ==father)
       continue;      
    if(niv[*it]==0)
      {stiva.push(make_pair(x,*it));
       niv[*it]=niv[x]+1;
       depth(*it,x);
       if(low[x]>low[*it])
          low[x]=low[*it];
       if(niv[x]<=low[*it])
          cbconex(x,*it);
       }
    else
      {low[x]=min(low[x],low[*it]);}   
       
    }
}

int main()
{f>>n>>m;
int x,y;
for(i=1; i<=m; i++)
  {f>>x>>y;
   a[x].push_back(y);
   a[y].push_back(x);}

for(i=1; i<=n; i++)
 if(niv[i]==0)
   {niv[i]=1;
    depth(i,0);}  

g<<nrcbc<<endl;

for(i=0; i<bigV.size(); i++)
  {for(j=(bigV[i].size()-1); j>=0; j--)
     g<<bigV[i][j]<<" ";
  g<<endl;}  
   
f.close();
g.close();
return 0;
}