Cod sursa(job #473496)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 29 iulie 2010 19:56:21
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <vector>
#include <cstdio>
#include <stack>
#define N 100001
#define INF 0x7fffffff
using namespace std;
vector<int> g[N];
vector<stack<int> >r;
stack<int> st;
int depth[N];
int reach[N];

void df(int k,int t,int d)
{int i;
 st.push(k);
 depth[k]=d;
 reach[k]=d;
 
 for (i=0;i<g[k].size();i++)
 {if(g[k][i]==t)continue;
  if(depth[g[k][i]]==-1)
  {df(g[k][i],k,d+1);
   if(reach[g[k][i]]>=d)
   {stack<int> s;
    while(st.top()!=k)
    {s.push(st.top());
     st.pop();
    }
    s.push(st.top());
    r.push_back(s);
   }
   else
   {if(reach[k]>reach[g[k][i]])
    {reach[k]=reach[g[k][i]];
    }
   }
  }
  else
  {if(reach[k]>reach[g[k][i]])
   {reach[k]=reach[g[k][i]];
   }
  }
 }
}

int main ()
{freopen("biconex.in","r",stdin);
 freopen("biconex.out","w",stdout);
 int n,m,i,x,y;
 scanf("%d %d",&n,&m);
 
 for (i=1;i<=m;i++)
 {scanf("%d %d",&x,&y);
  g[x].push_back(y);
  g[y].push_back(x);
 }
 
 for (i=1;i<=n;i++)
 {depth[i]=-1;
  reach[i]=INF;
 }
 
 df(1,0,0);
 
// for (i=1;i<=n;i++) {printf("%d %d %d\n",i,depth[i],reach[i]);}
 printf("%d\n",r.size());
 for (int i=0;i<r.size();i++)
 {while(!r[i].empty())
  {printf("%d ",r[i].top());
   r[i].pop();
  }
  printf("\n");
 }
 return 0;
}