Cod sursa(job #2351097)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 21 februarie 2019 23:01:16
Problema Mesaj4 Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>

#define MAXN 100005

int N, M, P[MAXN], Perm[MAXN];
std::vector <int> ADC[MAXN], TADC[MAXN];
std::vector <int> Leaves;

inline void AddEdge(int X, int Y) {
    ADC[X].push_back(Y);
    ADC[Y].push_back(X);
}

int Reach, LVL[MAXN];
void DFS(int Vertex = 1, int Level = 1) {
    ++ Reach;
    LVL[Vertex] = Level;
    for (auto Edge:ADC[Vertex])
        if (!LVL[Edge])
            DFS(Edge, Level+1), P[Edge] = Vertex, TADC[Vertex].push_back(Edge);
}

bool cmp(int idx, int idy) {
    return LVL[idx] < LVL[idy];
}

std::ifstream In ("mesaj4.in");
std::ofstream Out("mesaj4.out");

void Down(int Vertex) {
    for (auto Edge:ADC[Vertex]) {
        if (Vertex == P[Edge]) continue;
        Out << Vertex << ' ' << Edge << '\n';
        Down(Edge);
    }
}

void Print() {
    Out << 2*N-2 << '\n';
    for (int i=1; i<=N; ++i)
        Perm[i] = i;
    std::sort(Perm+1, Perm+N+1, cmp);

    for (int i=N; i>=2; --i)
        Out << Perm[i] << ' ' << P[Perm[i]] << '\n';
    for (int i=1; i<=N-1; ++i)
        for (auto Son:TADC[Perm[i]])
            Out << Perm[i] << ' ' << Son << '\n';
}

void Citire() {
    In >> N >> M;
    for (int i=1, X, Y; i<=M; ++i)
        In >> X >> Y, AddEdge(X, Y);
}

void Rezolvare() {
    DFS();
    if (Reach == N)
        Print();
    else
        Out << "-1\n";
}

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

    return 0;
}