Cod sursa(job #426065)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 26 martie 2010 13:24:45
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define FIN "biconex.in"
#define FOUT "biconex.out"
#define NMAX 100004
#include<vector>
vector<int> g[NMAX];
int n,m;

struct Stiva{int x,y;Stiva *next;};
typedef Stiva* st;
void push(st &q,int x,int y)
 {
     st p=new Stiva;
     p->x=x;
     p->y=y;
     p->next=q;
     q=p;
 }
void pop(st &q)
{
     st p;
     p=q;
     q=q->next;
     delete p;
     
     } 
st stack;     
vector < vector < int >  > rez;
int nivel[NMAX],low[NMAX];     
void dfs(int nod,int tata,int nv)     
{
     nivel[nod]=low[nod]=nv;
     vector<int>::iterator it;
     for(it=g[nod].begin();it!=g[nod].end();it++)
      {
      if(*it==tata) continue;
      if(nivel[*it]==-1) {push(stack,nod,*it);
                          dfs(*it,nod,nv+1);
                          low[nod]=min(low[*it],low[nod]);
                          if(low[*it]>=nivel[nod])
                             {
                              vector<int> aux;
                              int tx;int ty;
                              do
                                {tx=stack->x;
                                 ty=stack->y;
                                 aux.push_back(tx);aux.push_back(ty);
                                 pop(stack);
                                 }while(tx!=nod || ty!=*it);
                              rez.push_back(aux);    
                             }
                          
                         }                                           
      else low[nod]=min(low[nod],nivel[*it]);                                           
      }
     
     }
int viz[NMAX];     
int main()
{stack=new Stiva;
 freopen(FIN,"r",stdin);
 freopen(FOUT,"w",stdout);
  scanf("%d %d",&n,&m);
 for(int i=1;i<=m;i++)
  {int x,y;
   scanf("%d %d",&x,&y);
   g[x].push_back(y);
   g[y].push_back(x);
   } 
 for(int i=1;i<=n;i++) nivel[i]=-1;
 while(stack) pop(stack);
 dfs(1,0,0);
 printf("%d\n",rez.size());
 for(int i=0;i<rez.size();i++)
  {for(int k=1;k<=n;k++) viz[k]=0;
   for(int j=0;j<rez[i].size();j++)
     if(viz[rez[i][j]]==0) viz[rez[i][j]]=1,printf("%d ",rez[i][j]);
     printf("\n");
         }
 
    return 0;}