Cod sursa(job #987450)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 20 august 2013 18:42:05
Problema Tricouri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <fstream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

#define In "johnie.in"
#define Out "johnie.out"
#define Nmax 50004
#define pb push_back
#define Lim 1000000
#define Next ((++pos==Lim )? f.read(Buffer,Lim) ,pos = 0: 0)
using namespace std;

vector< int >Graph[Nmax],a;
vector< vector < int > > sol;
int n, m, degree[Nmax], pos;
ifstream f(In);
char Buffer[Lim];

inline void Read(int &x)
{
    x = 0;
    for(;Buffer[pos] < '0' || Buffer[pos] > '9'; Next);
    for(;Buffer[pos] >= '0' && Buffer[pos] <= '9'; Next)
        x = x*10+Buffer[pos]-'0';
}

inline void Read()
{
    f.read(Buffer,Lim);
    freopen(Out,"w",stdout);
    Read(n);Read(m);
    int i,x,y;
    for(i = 1 ;i <= m ; ++i)
    {
        Read(x);Read(y);
        Graph[x].pb(y);
        Graph[y].pb(x);
        ++degree[x];
        ++degree[y];
    }
}

inline void Dfs(int node)
{
    stack< int >St;
    St.push(node);
    int y;
    while(!St.empty())
    {
        node = St.top();
        if(!Graph[node].size())
        {
            St.pop();
            if(node==0)
            {
                sol.pb(a);
                a.clear();
            }
            else
                a.pb(node);
        }
        else
        {
            y = Graph[node].back();
            St.push(y);
            Graph[node].pop_back();
            Graph[y].erase(find(Graph[y].begin(),Graph[y].end(),node));
        }
    }
}

inline void Solve()
{
    for(int i = 1;i <= n; ++i)
        if(degree[i]&1)
        {
            Graph[0].pb(i);
            Graph[i].pb(0);
        }
    Dfs(0);
}

inline void Write()
{
    int k = sol.size();
    printf("%d\n",k-1);
    vector<int >::iterator it;
    for(int i = 1;i < k; ++i)
    {
        printf("%d ",sol[i].size());
        for(it = sol[i].begin();it!=sol[i].end();++it)
            printf("%d ",*it);
        printf("\n");
    }
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}