Cod sursa(job #1223710)

Utilizator tester_31tester tester_31 Data 28 august 2014 17:31:13
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.7 kb
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<vector>
#include<stack>
using namespace std;
const int maxn = 50004;
const int maxm = 100005;

vector <int> a[maxn];
vector <int> sol[maxm];
stack <int> st;

int nr_grad_impar,nr_conexe_cicluri,etape;
int i,j,n,m,x,y,nr;
bool este,viz[maxn];

void dfs(int nod){
     if(a[nod].size()&1) este=0;
     viz[nod]=1;
     for(int j=0;j<(int)a[nod].size();j++)
       if(!viz[a[nod][j]]) dfs(a[nod][j]);
}

void euler(const int x){

     st.push(x);
     while(!st.empty())
          {
           int nod=st.top();
           if(a[nod].size()){
                             int vecin=a[nod].back();
                             a[nod].pop_back();
                             
                             int j=a[vecin].size()-1;
                             while(j>=0 && a[vecin][j]!=nod) j--;
                             a[vecin][j]=a[vecin].back();
                             a[vecin].pop_back();
                             
                             st.push(vecin);
                            }
           else{//nu mai am vecini
                st.pop();
                if(nod) sol[nr].push_back(nod);//nu adaug nodul 0
                else nr++;
               }
          }
}


int main(void){
    assert(freopen("johnie.in","r",stdin));
    assert(freopen("johnie.out","w",stdout));

    assert(scanf("%d %d",&n,&m)==2);
    for(i=1;i<=m;i++){
                      assert(scanf("%d %d",&x,&y)==2);
                      a[x].push_back(y);
                      a[y].push_back(x);
                     }
    
    for(i=1;i<=n;i++) viz[i]=0;
    for(i=1;i<=n;i++)
      if(!viz[i] && a[i].size()){ 
                                 este=1; 
                                 dfs(i); 
                                 nr_conexe_cicluri+=este; 
                                }
      
    for(i=1;i<=n;i++)
      if(a[i].size()&1){//unesc nodul 0 cu nodurile cu grad impar
                        nr_grad_impar++; 
                        a[0].push_back(i); 
                        a[i].push_back(0); 
                       } 
    
    etape = nr_conexe_cicluri + nr_grad_impar/2;

    printf("%d\n",etape);
    
    nr=0;  
    euler(0);
    
    if(nr_conexe_cicluri){//adaug si componentele conexe care sunt cicluri (daca exista)  
                          for(i=1;i<=n;i++)
                            if(a[i].size()) euler(i);
                         }

    for(i=1;i<=etape;i++)
       {
        printf("%d ",sol[i].size());
        for(j=0;j<(int)sol[i].size();j++) printf("%d ",sol[i][j]);
        printf("\n");
       }

    fclose(stdin);
    fclose(stdout);
    return 0;
}