Cod sursa(job #1366965)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 1 martie 2015 15:10:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <stdio.h>
#include <vector>
#include <utility>

#define NN 100008
#define MN 200008
#define mp make_pair
#define lf (*l).first
#define ld (*l).second

using namespace std;


vector <pair <int,int> > drum, bi[NN];
vector <pair <int,int> >:: iterator l;
vector <int> a[NN];
int tata[NN],d[NN],low[NN],C[NN],nr,n,m,x,y,i,ct,CT,j;
bool use[NN];
void dfs(int k){
vector <int>::iterator it;

d[k]=++nr;
low[k]=d[k];

for(it=a[k].begin();it!=a[k].end();++it){
if (d[*it]==0){
 drum.push_back(mp(k,*it));
 tata[*it]=k;
 dfs(*it);
 low[k]=min(low[k],low[*it]);
 if (low[*it]>=d[k]){
  l=drum.end()-1;
  ++ct;
  while((*l).first!=k && (*l).second!=*it){bi[ct].push_back(*l);drum.pop_back();l=drum.end()-1;}
  bi[ct].push_back(*l);
  drum.pop_back();
}
}
else if (tata[k]!=*it){low[k]=min(low[k],d[*it]);/*drum.push_back(mp(k,*it));*/}

}


}

int main()
{
freopen("biconex.in", "r",stdin);
freopen("biconex.out", "w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
 scanf("%d%d",&x,&y);
 a[x].push_back(y);
 a[y].push_back(x);
}
dfs(1);
printf("%d\n",ct);
for(i=1;i<=n;i++){
CT=0;
  for(l=bi[i].begin();l!=bi[i].end();++l) {

  if (use[lf]==false){printf("%d ",lf);use[lf]=true;C[++CT]=lf;}
  if (use[ld]==false){printf("%d ",ld);use[ld]=true;C[++CT]=ld;}
  }

for(j=1;j<=CT;j++)
use[C[j]]=false;
printf("\n");
}

 return 0;
}