Cod sursa(job #2252552)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 2 octombrie 2018 20:06:24
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <bits/stdc++.h>

#define MaxN 100005
#define MaxM 500005

std::ifstream InFile("ciclueuler.in");
std::ofstream OutFile("ciclueuler.out");

template <int NNodes, int NEdges>
struct GraphStruct {
    int N, M;
    std::vector <std::pair <int, int>> Edges;
    struct NodeStruct {
        int Grad;
        std::vector <int> Edges;
    }   Node[NNodes];

    inline void AddEdge(int x, int y, int EdgeIndex) {
        Node[x].Edges.push_back(EdgeIndex);
        Node[y].Edges.push_back(EdgeIndex);
        Node[x].Grad++; Node[y].Grad++;
        Edges.push_back(std::make_pair(x, y));
    }

    bool Preelim() {
        for (int i=0; i<N; i++)
            if (Node[i+1].Grad%2 == 1) return 0;
        return 1;
    }

    int P[MaxN];
    bool Used[NEdges];
    std::vector <int> Ciclu;
    void DFS(int Index) {
        int EdgeIndex;

        while(P[Index] < Node[Index].Edges.size()) {
            EdgeIndex = Node[Index].Edges[P[Index]++];
            if (!Used[EdgeIndex]) {
                Used[EdgeIndex] = 1;
                DFS(Edges[EdgeIndex].first + Edges[EdgeIndex].second - Index);
            }
        }   Ciclu.push_back(Index);
    }

    void FindEulerian() {
        DFS(Edges[0].first);
        for (int i=1; i<Ciclu.size(); ++i)
            OutFile << Ciclu[i] << ' ' ;
    }

};  GraphStruct <MaxN, MaxM> Graph;

void Citire() {
    InFile >> Graph.N >> Graph.M;
    for (int i=0, x, y; i<Graph.M; i++)
        InFile >> x >> y,
        Graph.AddEdge(x, y, i);
}
void Rezolvare() {
    if(Graph.Preelim())
        Graph.FindEulerian();
    else OutFile << "-1\n";
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}