Cod sursa(job #240865)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 8 ianuarie 2009 20:31:41
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define pb push_back
#define u first
#define v second
const int NMAX=100001;
vector<int> Adj[NMAX],a;
int N,M,nr,d[NMAX],low[NMAX];
vector< vector<int> > C;
stack< pair<int,int> > s;
vector< pair<int,int> > b;
bool U[NMAX];
void df(int vf){
     vector<int>::iterator it;
     int x,y;
     low[vf]=d[vf];
     for (it=Adj[vf].begin();it!=Adj[vf].end();++it) 
      if (!d[*it]){
        d[*it]=d[vf]+1;
        s.push(make_pair(vf,*it));
        df(*it);
        if (low[*it]>=d[vf])
        {
         ++nr;
         
         b.clear();
         do {
           b.pb(s.top());
           x=s.top().u;
           y=s.top().v;
           s.pop();
            }
         while (x!=vf || y!=*it);
         
         a.clear();
         for (size_t i=0;i<b.size();++i)
          U[b[i].u]=U[b[i].v]=false;
         for (size_t i=0;i<b.size();++i){
          if (!U[b[i].u]) a.pb(b[i].u);
          if (!U[b[i].v]) a.pb(b[i].v);
          U[b[i].u]=U[b[i].v]=true;} 
         
         C.pb(a);
        }
        low[vf]=min(low[vf],low[*it]);
        }
      else if (d[vf]-1!=d[*it]) low[vf]=min(low[vf],low[*it]);
      }
int main(){
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int i,j;
    
    fin>>N>>M;
    while (M--){
      fin>>i>>j;
      Adj[i].pb(j);
      Adj[j].pb(i);}
      
    d[1]=1;
    df(1);
    
    fout<<nr<<'\n';
    for (i=0;i<nr;++i){
      for (j=0;j<(int)C[i].size();++j)
        fout<<C[i][j]<<' ';
      fout<<'\n';}
    return 0;
}