#include #include #include #define MAXN 100000 #define MAXM 500000 #define SWAP_INT(x, y) { int tmp = x; x = y; y = tmp; } /* Struktura uchovávající údaje o jedné hraně */ struct s_edge { int a, b; // Mezi kterými vrcholy hrana vede. int pair; // Se kterou hranou je spárovaná (-1, pokud ještě není). }; /* Pocatek hran od daneho vrcholu v seznamu hran a stupen vrcholu */ struct s_vertex { int start; // Index první hrany v seznamu hran (resp. poli "ep"), která inciduje s tímto vrcholem. int deg; // Stupeň vrcholu. int visited; // Zda již byl vrchol navštíven. }; /* Globální proměnné */ struct s_edge edges[MAXM]; // Seznam hran (tak jak je načten ze souboru). struct s_vertex vertices[MAXN]; // Seznam vrcholů. int ep[2*MAXM]; // Přeuspořádání hran (aby bylo možné jednoduše držet seznamy sousedů). int N, M; // Počet vrcholů a hran. /* Načte vstupní data a vytvoří reprezentaci grafu. */ void read_input(void) { /* Otevřeme soubor */ FILE *fp = fopen("asfalt.in", "r"); if (!fp) { perror("Cannot open input file"); exit(1); } /* Přečteme počet vrcholů a hran. */ fscanf(fp, "%d %d", &N, &M); /* Ošetříme speciální případ, kdy je M liché a úloha tak nemá řešení. */ if ((M % 2) == 1) { FILE *fout = fopen("asfalt.out", "w"); if (!fout) { perror("Cannot open output file"); exit(1); } fputs("no\n", fout); exit(0); } /* Načteme seznam hran */ for (int i = 0; i < M; i++) { fscanf(fp, "%d %d", &edges[i].a, &edges[i].b); edges[i].a--; edges[i].b--; // V našem programu indexujeme města od 0 do N-1. edges[i].pair = -1; // -1 značí, že hrana ještě není spárovaná. vertices[edges[i].a].deg++; vertices[edges[i].b].deg++; } fclose(fp); /* Vybudujeme si index ep nad polem hran, díky kterému budeme mít jednoduchý seznam sousedů. */ for (int i = 1; i < N; i++) { vertices[i].start = vertices[i-1].start+vertices[i-1].deg; vertices[i-1].deg = 0; } vertices[N-1].deg = 0; for (int i = 0; i < M; i++) { ep[ vertices[edges[i].a].start + vertices[edges[i].a].deg++ ] = i; ep[ vertices[edges[i].b].start + vertices[edges[i].b].deg++ ] = i; } } /* Vrátí druhý konec hrany edge incidující s vrcholem vertex. */ inline int edge_end(int vertex, int edge) { if (edges[edge].a != vertex) return edges[edge].a; return edges[edge].b; } /* Uloží výsledky do výstupního souboru. */ void print_out(void) { /* Otevřeme výstupní soubor. */ FILE *fout = fopen("asfalt.out", "w"); if (!fout) { perror("Cannot open output file"); exit(1); } /* Vytiskneme spárované hrany. */ for (int i = 0; i < M; i++) if (edges[i].pair > i) { int res[4] = { edges[i].a, edges[i].b, edges[edges[i].pair].a, edges[edges[i].pair].b }; if ((res[0] == res[2]) || (res[0] == res[3])) SWAP_INT(res[0], res[1]) if ((res[0] == res[3]) || (res[1] == res[3])) SWAP_INT(res[2], res[3]) fprintf(fout, "%d %d %d\n", res[0]+1, res[1]+1, res[3]+1); } fclose(fout); } /* Prohledávání do hloubky na párování hran. */ void dfs(int actVertex, int parent) { vertices[actVertex].visited = 1; // Takhle označíme prohledávaný vrchol za navštívený. /* Zavolame se na vsechny sousedni vrcholy, ve kterych jsme dosud nebyli */ for (int i = vertices[actVertex].start; i < vertices[actVertex].start + vertices[actVertex].deg; i++) if (!vertices[edge_end(actVertex, ep[i])].visited) dfs(edge_end(actVertex, ep[i]), actVertex); /* Nyní spárujeme zbylé hrany. */ int pair = -1; for (int i = vertices[actVertex].start; i < vertices[actVertex].start + vertices[actVertex].deg; i++) if ((edges[ep[i]].pair == -1) && edge_end(actVertex, ep[i]) != parent) { if (pair == -1) // Zatím nemame hranu ke spárování... pair = ep[i]; else { // Už na nás jedna nespárovaná hrana čeká. edges[ep[i]].pair = pair; edges[pair].pair = ep[i]; pair = -1; } } /* Pokud jedna hrana zbyla plonková - spárujeme ji s hranou k rodiči. */ if (pair != -1) { /* Bohužel hranu k otci musíme nejdřív najít... */ int i = vertices[actVertex].start; while (edge_end(actVertex, ep[i]) != parent) i++; /* Index hrany k otci je teď uložen v i. */ edges[ep[i]].pair = pair; edges[pair].pair = ep[i]; } } /* Vstupní bod aplikace. */ int main(void) { read_input(); dfs(0, 0); print_out(); return 0; }