Cod sursa(job #260069)

Utilizator MciprianMMciprianM MciprianM Data 16 februarie 2009 15:26:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define MAXN    100001
struct muchie{int e1, e2;};
int n, m;
vector<int> G[MAXN];
vector< vector<int> > bic;
int desc[MAXN],mlevel[MAXN];
stack<muchie> stiva;
muchie muc;
void afis(int x, int y){
  vector<int> linie;
  muchie mi;
  do{
    mi=stiva.top();
    stiva.pop();
    linie.push_back(mi.e1);
    linie.push_back(mi.e2);
  }while(mi.e1!=x||mi.e2!=y);
  sort(linie.begin(), linie.end());
  linie.erase(unique(linie.begin(), linie.end()), linie.end());
  bic.push_back(linie);
}
void df(int nod,int tnod, int nivel){
  vector<int>::iterator it;
  desc[nod]=mlevel[nod]=nivel;
  for(it=G[nod].begin();it!=G[nod].end();++it){
    if(!desc[*it]){
      muc.e1=nod;muc.e2=*it;
      stiva.push(muc);
      df(*it, nod, nivel+1);
      if(mlevel[*it]<mlevel[nod])
        mlevel[nod]=mlevel[*it];
      if(mlevel[*it]>=nivel) afis(nod, *it);
    }
    else{
      if(*it!=tnod&&desc[*it]<mlevel[nod])
             mlevel[nod]=desc[*it];
    }
  }
}

int main(){
  int nrcmp;
  int i, x, y;
  vector<int>::iterator it;
  ifstream f("biconex.in");
  f>>n>>m;
  for(i=0;i<m;i++){
    f>>x>>y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  f.close();
  df(1,0,1);
  nrcmp=bic.size();
  ofstream g("biconex.out");
  g<<nrcmp<<'\n';
  for(i=0;i<nrcmp;i++){
    for(it=bic[i].begin();it!=bic[i].end();++it)
      g<<*it<<' ';
    g<<'\n';
  }
  g.close();
  return 0;
}