Kódy nejrychlejších řešení viz níže.
Relativní čas vůči referenčnímu řešení se počítá tak, že se sečtou v posledním odevzdaném studentském řešení všechny časy na neveřejných souborech ( časStud ), všechny časy na na neveřejných souborech v referenčním řešení ( časRef ) a spočte se podíl časStud/časRef. Zveřejňujeme pouze časy řešitelů, kteří dosáhli na 10/10. Časy řešení v některých instancích pomalých nebo chybných pravděpodobně nejsou směrodatné.
řešitel jazyk relativní čas vůči referenčnímu řešení truondom C | 10 0.072 preister C | 10 0.075 krivapa2 C | 10 0.077 pazouma1 Cpp | 10 0.089 hrubype7 Cpp | 10 0.093 bilanmak Cpp | 10 0.096 dzivjmat Cpp | 10 0.099 kubackri Cpp | 10 0.101 janatpa3 Cpp | 10 0.102 zacekpe2 Cpp | 10 0.104 brezipat Cpp | 10 0.105 ngothien Cpp | 10 0.106 voracva1 Cpp | 10 0.108 stoklji1 C | 10 0.109 glingvla C | 10 0.112 skoreja5 C | 10 0.118 rysavji2 C | 10 0.123 neckavit Cpp | 10 0.127 cernypro Cpp | 10 0.136 jakouto3 Cpp | 10 0.137 simanvo1 Cpp | 10 0.141 maderja1 C | 10 0.149 buchnmic Cpp | 10 0.161 skalaja7 Cpp | 10 0.163 simonrob C | 10 0.165 mikulpa6 Cpp | 10 0.168 manousim Cpp | 10 0.171 mertahan C | 10 0.173 rimalma1 Cpp | 10 0.178 klimema4 C | 10 0.179 skalajoz Cpp | 10 0.179 pultami1 Cpp | 10 0.185 juraspat Cpp | 10 0.189 kolinvo2 Cpp | 10 0.193 proksmi1 Cpp | 10 0.194 brejcka1 Cpp | 10 0.201 lebeddar Cpp | 10 0.203 hvezdmic Cpp | 10 0.209 safarjar C | 10 0.219 matijmic Cpp | 10 0.223 bugosjoz Cpp | 10 0.241 filomich Cpp | 10 0.251 jakeskla C | 10 0.268 borakdan C | 10 0.288 stupaily Cpp | 10 0.299 lasstani Cpp | 10 0.329 bednabo1 Cpp | 10 0.503 konopkla Java | 10 0.556 gritsdmi Cpp | 10 0.565 klanjan Java | 10 0.599 klochmik Cpp | 10 0.619 seberma3 Cpp | 10 0.719 kynclmat Python | 10 0.771 repamart C | 10 0.833 turynmar Java | 10 0.843 zahraji3 Cpp | 10 0.844 kratoon3 Java | 10 0.864 buitiepq Cpp | 10 0.872 nejtejan Java | 10 0.886 zakhuvia Cpp | 10 0.925 kalinja6 Java | 10 0.959 klemema4 Java | 10 1.080 ivashmak Java | 10 1.092 tichama6 Java | 10 1.128 filipcsa Java | 10 1.173 ottastep Java | 10 1.176 forstluk Java | 10 1.215 szaboeme Java | 10 1.248 trnkavla Java | 10 1.344 kubismi5 Java | 10 1.371 jirmaja1 Java | 10 1.383 sadloric Java | 10 1.493 brazddom Java | 10 1.547 tributib Java | 10 1.667 kostkpe3 Java | 10 1.680 matocmir Java | 10 1.710 kuzevigo Java | 10 1.859
#include <stdio.h> #include <stdlib.h> #include <time.h> #define TRUE 1 #define FALSE 0 typedef struct { int size; int capacity; int *neighbors; } node_t; typedef struct { int size; int capacity; int head; int tail; int *nodes; } queue_t; typedef struct { int size; int *nodes; } visited_t; inline void scanint(int *x); node_t *read_nodes(int numb_nodes, int numb_conn); void init_nodes(node_t *nodes, int numb_nodes); void add_neighbor(node_t *nodes, int idx, int neigh); void deallocate_memory(node_t *nodes, int numb_nodes); void init_queue(queue_t *queue, int numb_nodes); void push_queue(queue_t *queue, int value); int pop_queue(queue_t *queue); int queue_empty(queue_t *queue); int visited_func(visited_t *visited, int node); int is_socket(node_t *nodes, int numb_nodes, int start_node, visited_t *visited, queue_t *queue, int *parents, int *curr_nodes); int is_parent(int *parents, int numb_parents, int value); void free_memory(visited_t *visited, int *parents, int *curr_nodes, queue_t *queue); int main(int argc, char **argv) { int numb_nodes, numb_conn, numb_sockets = 0, *sockets, *parents, *curr_nodes; node_t *nodes; visited_t visited; queue_t *queue; //clock_t start = clock(); scanint(&numb_nodes); scanint(&numb_conn); numb_nodes++; nodes = read_nodes(numb_nodes, numb_conn); sockets = (int *)malloc(numb_nodes * sizeof(int)); visited.nodes = (int *)malloc(numb_nodes * sizeof(int)); parents = (int *)malloc(numb_nodes * sizeof(int)); curr_nodes = (int *)malloc(numb_nodes * sizeof(int)); queue = (queue_t *)malloc(sizeof(queue_t)); queue->nodes = (int *)malloc(numb_nodes * sizeof(int)); for (int i = 1; i < numb_nodes; i++) { if (nodes[i].size == 2 && is_socket(nodes, numb_nodes, i, &visited, queue, parents, curr_nodes)) { sockets[numb_sockets++] = i; } } if (numb_sockets == numb_nodes-1) { int node = sockets[0]; int prev = node; printf("%d", node); node = nodes[node].neighbors[0]; for (int i = 0; i < (numb_nodes)/2+1; i++) { node = (nodes[node].neighbors[0] == prev) ? nodes[node].neighbors[0] : nodes[node].neighbors[1]; prev = node; } printf(" %d\n", node); } else { int max = (numb_sockets > 100) ? 100 : numb_sockets; for (int j = 0; j < max; j++) { if (j == 0) { printf("%d", sockets[j]); } else { printf(" %d", sockets[j]); } } printf("\n"); } deallocate_memory(nodes, numb_nodes); free_memory(&visited, parents, curr_nodes, queue); free(sockets); //clock_t end = clock(); //float seconds = (float)(end - start) / CLOCKS_PER_SEC; //printf("Time: %f seconds\n", seconds); return 0; } inline void scanint(int *x) { register char c = getchar_unlocked(); *x = 0; for(; (c<48)||(c>57);c = getchar_unlocked()); for(; (c>47)&&(c<58);c = getchar_unlocked()) *x = (int)((((*x)<<1) + ((*x)<<3)) + c - 48); } node_t *read_nodes(int numb_nodes, int numb_conn) { node_t *nodes = (node_t *)malloc(numb_nodes * sizeof(node_t)); init_nodes(nodes, numb_nodes); for (int i = 0; i < numb_conn; i++) { int node1, node2; scanint(&node1); scanint(&node2); add_neighbor(nodes, node1, node2); add_neighbor(nodes, node2, node1); } return nodes; } void init_nodes(node_t *nodes, int numb_nodes) { for (int i = 0; i < numb_nodes; i++) { nodes[i].neighbors = (int *)malloc(10 * sizeof(int)); nodes[i].size = 0; nodes[i].capacity = 10; } } void add_neighbor(node_t *nodes, int idx, int neigh) { if (nodes[idx].size == nodes[idx].capacity) { nodes[idx].capacity *= 2; nodes[idx].neighbors = (int *)realloc(nodes[idx].neighbors, nodes[idx].capacity * sizeof(int)); } nodes[idx].neighbors[nodes[idx].size++] = neigh; } void deallocate_memory(node_t *nodes, int numb_nodes) { for (int i = 0; i < numb_nodes; i++) { free(nodes[i].neighbors); } free(nodes); } void init_queue(queue_t *queue, int numb_nodes) { queue->size = 0; queue->capacity = numb_nodes; queue->head = queue->tail = 0; } void push_queue(queue_t *queue, int value) { if (queue_empty(queue)) { queue->head = queue->tail = 0; queue->nodes[queue->tail++] = value; queue->size++; } else { queue->nodes[queue->tail] = value; queue->tail = (queue->tail + 1) % queue->capacity; queue->size++; } } int pop_queue(queue_t *queue) { int ret; if (queue_empty(queue)) { ret = -1; } else { ret = queue->nodes[queue->head]; queue->head = (queue->head + 1) % queue->capacity; queue->size--; } return ret; } int queue_empty(queue_t *queue) { return queue->size == 0; } int visited_func(visited_t *visited, int node) { for (int i = 0; i < visited->size; i++) { if (visited->nodes[i] == node) { return TRUE; } } return FALSE; } int is_parent(int *parents, int numb_parents, int value) { for (int i = 0; i < numb_parents; i++) { if (parents[i] == value) return TRUE; } return FALSE; } void free_memory(visited_t *visited, int *parents, int *curr_nodes, queue_t *queue) { free(visited->nodes); free(parents); free(curr_nodes); free(queue->nodes); free(queue); } int is_socket(node_t *nodes, int numb_nodes, int start_node, visited_t *visited, queue_t *queue, int *parents, int *curr_nodes) { int numb_parents = 0, numb_curr_nodes = 0, tmp = 0; visited->size = 0; init_queue(queue, numb_nodes); push_queue(queue, start_node); visited->nodes[visited->size++] = start_node; parents[numb_parents++] = start_node; numb_curr_nodes++; while (!queue_empty(queue)) { int sum = 0, sum1 = 0, sum2 = 0; for (int i = 0; i < numb_curr_nodes; i++) { curr_nodes[i] = pop_queue(queue); sum += nodes[curr_nodes[i]].size; if (numb_curr_nodes == 1) { sum1+= nodes[curr_nodes[i]].size; sum2+= nodes[curr_nodes[i]].size; } else if (i < numb_curr_nodes/2) { sum1+= nodes[curr_nodes[i]].size; } else { sum2+= nodes[curr_nodes[i]].size; } } if (sum % 2 == 1) { return FALSE; } if (sum1 != sum2) { return FALSE; } tmp = 0; for (int i = 0; i < numb_curr_nodes; i++) { for (int j = 0; j < numb_curr_nodes; j++) { if (i != j) { for (int x = 0; x < nodes[curr_nodes[i]].size; x++) { for (int y = 0; y < nodes[curr_nodes[j]].size; y++) { if (nodes[curr_nodes[i]].neighbors[x] == nodes[curr_nodes[j]].neighbors[y] && !is_parent(parents, numb_parents, nodes[curr_nodes[i]].neighbors[x])) { if (nodes[nodes[curr_nodes[i]].neighbors[x]].size == 2 && nodes[curr_nodes[i]].size == nodes[curr_nodes[j]].size) { return TRUE; } else { return FALSE; } } } } } } for (int j = 0; j < nodes[curr_nodes[i]].size; j++) { if (!visited_func(visited, nodes[curr_nodes[i]].neighbors[j])) { visited->nodes[visited->size++] = nodes[curr_nodes[i]].neighbors[j]; push_queue(queue, nodes[curr_nodes[i]].neighbors[j]); tmp++; } } parents[numb_parents++] = curr_nodes[i]; } numb_curr_nodes = tmp; } return FALSE; }
#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <time.h> int nodes; unsigned char *visited_from; unsigned char *done_socket; unsigned char *visited; unsigned char *side; int *queue; int bfs_count = 0; int done = 0; int rear = 0; struct node { int value; struct node* next; }; struct Graph { struct node** adjLists; int numElements; }; struct node* createNode(int vertex) { struct node* newNode = malloc(sizeof(struct node)); newNode->next = NULL; newNode->value = vertex; return newNode; } //pridani hran void addEdge(struct Graph* graph, int src, int dest) { //pridavam hranu z prvniho prvku do druheho struct node* newNode = createNode(dest); newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode; //pridavam hranu z druheho prvku do prvniho newNode = createNode(src); newNode->next = graph->adjLists[dest]; graph->adjLists[dest] = newNode; } //vytvorim adjacency List o "elements" prvcich struct Graph* createGraph(int elements) { struct Graph* graph = malloc(sizeof(struct Graph)); graph->numElements = elements; graph->adjLists = malloc(elements * sizeof(struct node*)); for (int i = 0; i < elements; i++) graph->adjLists[i] = NULL; // prozatim na NULL return graph; } //prohleda mi adjacency List do sirky a vrati sokety void bfs(int v, struct Graph* graph) { int front = 0; rear = 0; if (bfs_count == 0) { for (int i=0; i<nodes; i++) { //resi mi spravne levo a pravo, jinak byly problemy s 0 queue[i] = -1; } bfs_count =1; } else { for (int i=0; i<nodes; i++) { queue[i] = -1; side[i] = 0; } memcpy(visited,side,sizeof(unsigned char)*nodes); memcpy(visited_from,side,sizeof(unsigned char)*nodes); memcpy(done_socket,side,sizeof(unsigned char)*nodes); } visited[v] = 1; visited_from[v] = 1; queue[rear] = v; rear++; //konec while (rear != front) {//dokud fronta neni plna/prazdna int u = queue[front]; //prvni prvek, ktery byl zvolen visited_from[u] = 1; front++; struct node* temp = graph->adjLists[u]; while (temp) //dokud prvek s necim sousedi { if(!visited_from[temp->value]) { //pokud uz jsem z nej neprohledavala if (!visited[temp->value]) { queue[rear] = temp->value; //prvek prochazim ze strany, odkud byl jeho rodic if (rear == 1) { side[temp->value] = 2; } if (rear == 2) { side[temp->value] = 3; } if (front>=2) { side[temp->value] = side[u]; } rear++; visited[temp->value] = 1; } else { //"opakujici se prvek" - mozny soket unsigned char now_side_new = side[u]; if (now_side_new == side[temp->value]) { //prvek byl navstiven ze stejne strany, koncim bfs return; } //kontrola podezreleho soketu na presne dve hrany struct node* suspected = graph->adjLists[temp->value]; int suspect_counter = 0; while (suspected) { suspect_counter++; if (suspect_counter>2) { return; } suspected = suspected->next; } if (suspect_counter != 2) { return; } //prosel vsemi kontrolami, je to mozny soket done_socket[temp->value]=1; } } temp = temp->next; } } done = 1; printf("%d", v);//to je muj zvoleny soket int socket_counter=0; for (int f=0; f<nodes; f++) { if (socket_counter == 99) { break; } if(done_socket[f] == 1) { socket_counter++; printf(" %d", f);} } printf("\n"); } int main(int argc, char *argv[]) { /* clock_t start = clock(); */ int connections; int first_connected; int second_connected; if (scanf("%d %d", &nodes, &connections) != 2) { printf("Input is wrong!"); return 2; } nodes++; struct Graph* graph = createGraph(nodes); visited = calloc(nodes, sizeof(unsigned char)); visited_from = calloc(nodes, sizeof(unsigned char)); done_socket = calloc(nodes, sizeof(unsigned char)); queue = calloc(nodes, sizeof(int)); side = calloc(nodes, sizeof(unsigned char)); //plnim adj. graf for (int i=0; i< connections; i++) { scanf("%d %d", &first_connected, &second_connected); addEdge(graph, first_connected, second_connected); } for (int i=1; i<nodes;i++) { if (done == 1) { break; } int neigbour_counter = 0; int wrong = 0; int once = 0; int neigbour_one = 0; int neigbour_two = 0; struct node* temp = graph->adjLists[i]; while (temp) { once = 1; if (neigbour_counter == 0) { neigbour_one = temp->value; } else { neigbour_two = temp->value; } if (neigbour_counter >= 2) { //zkousim, jestli ma presne sousedy wrong = 1; break;} neigbour_counter++; temp = temp->next; } if (neigbour_two == 0) {wrong = 1;} if (wrong != 1) { //zkousim, zda sousedi maji stejny pocet sousedu int n1 = 0; int n2 = 0; struct node* neigbour1 = graph->adjLists[neigbour_one]; struct node* neigbour2 = graph->adjLists[neigbour_two]; while (neigbour1) { n1++; neigbour1 = neigbour1->next; } while (neigbour2) { n2++; neigbour2 = neigbour2->next; if (n2>n1) { wrong = 1; break; } } if ((n1 == n2) && (wrong == 0) && (once == 1)) { //mozny soket, zacnu z nej bfs bfs(i, graph); } } } free(visited); free(visited_from); free(queue); free(side); free(done_socket); /* clock_t end = clock(); float seconds = (float)(end - start) / CLOCKS_PER_SEC; printf("\n%f\n", seconds); */ return 0; }
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> typedef struct Node { int hodnota; struct Node* next; } Node_t; typedef struct Pole { struct Node *pocatekPole; } Pole_t; typedef struct Graf { int pocetUzlu; struct Pole* pole; } Grafik_t; Grafik_t* udelejGrafa (int pocetUzlu) { Grafik_t* Graf = (Grafik_t*) malloc (1 * sizeof(Grafik_t)); Graf->pocetUzlu = pocetUzlu; Graf->pole = (Pole_t*) malloc (pocetUzlu * sizeof(Pole_t)); int i = 1; while (i < pocetUzlu) { Graf->pole[i].pocatekPole = NULL; i = i + 1; } return Graf; } void pridejUzlik (Grafik_t* Graf, int uzel1, int uzel2, int kolik) { Node_t* novyUzel = (Node_t*) malloc (1 * sizeof(Node_t)); novyUzel->hodnota = uzel2; novyUzel->next = Graf->pole[uzel1].pocatekPole; Graf->pole[uzel1].pocatekPole = novyUzel; Node_t* novyUzel2 = (Node_t*) malloc (1 * sizeof(Node_t)); novyUzel2->hodnota = uzel1; novyUzel2->next = Graf->pole[uzel2].pocatekPole; Graf->pole[uzel2].pocatekPole = novyUzel2; } int doesItHaveTwoNeighbours (int i, Grafik_t* Graf, int N) { int sum = 0; while (i < N+1) { if (sum == 2) { return i-1; } sum = 0; Node_t *uzel = Graf->pole[i].pocatekPole; while (uzel != NULL) { sum++; uzel = uzel->next; } i = i + 1; } return 0; } int howManyNeighbours (int i, Grafik_t* Graf) { int sum = 0; Node_t *uzel = Graf->pole[i].pocatekPole; while (uzel != NULL) { sum++; uzel = uzel->next; } return sum; } bool doesItHaveSameNumberOfNeighboursNeighbours (int potentialSocket, Grafik_t *Graf) { int SousedPrvni = Graf->pole[potentialSocket].pocatekPole->hodnota; int SousedDruhy = Graf->pole[potentialSocket].pocatekPole->next->hodnota; int pocetSouseduPrvniho = howManyNeighbours(SousedPrvni, Graf); int pocetSouseduDruheho = howManyNeighbours(SousedDruhy, Graf); if (pocetSouseduPrvniho == pocetSouseduDruheho) { return true; } return false; } int* bfs (int *q, bool *visited, int * smer, int v, Grafik_t* Graf, int rear, int front) { int *possibleSokety = (int*) calloc (Graf->pocetUzlu, sizeof(int)); visited[v] = true; q[rear] = v; possibleSokety[v] += 2; rear++; int prvniPruchod = 0; while (rear != front) { int u = *(q+front); front++; visited[u] = 1; Node_t *prochazeny = Graf->pole[u].pocatekPole; while (prochazeny != NULL) { int hodnota = prochazeny->hodnota; q[rear] = hodnota; if (!visited[hodnota]) { q[rear] = hodnota; rear++; possibleSokety[hodnota]++; if (prvniPruchod == 0) { smer[hodnota]++; prvniPruchod = 1; } else if (prvniPruchod == 1) { smer[hodnota]--; prvniPruchod = 2; } if (smer[u] > 0) { smer[hodnota]++; } else if (smer[u] < 0) { smer[hodnota]--; } if (smer[hodnota] == 2 || smer[hodnota] == -2) { return NULL; } } prochazeny = prochazeny->next; } } return possibleSokety; } int* checkResultik (int pocatek, int * smer, int *possibleSokety, Grafik_t* Graf) { int count = 1; if (possibleSokety == NULL) { return NULL; } int *Sokety = calloc (101, sizeof(int)); for (int i = 1; i < Graf->pocetUzlu; i++) { if (possibleSokety[i] == 2 && smer[i] == 0 && howManyNeighbours(i, Graf)== 2) { Sokety[count] = i; count++; if (count > 100) { return Sokety; } continue; } else if (smer[i] == -2 || smer[i] == 2 || possibleSokety[i] > 2) { return NULL; } } if (count > 1) { return Sokety; } return NULL; } int main () { int N, M; //N uzly, M spojeni scanf("%i %i", &N, &M); // nacitani do listu Grafik_t* Graf = udelejGrafa (N+1); int prvni, druhy; for (int n = 0; n < M; n++) { scanf("%d %d", &prvni, &druhy); pridejUzlik (Graf, prvni, druhy, n); } bool *visited = (bool*) calloc(N+1, sizeof(bool)); int *smer = (int*) calloc (N+1, sizeof(int)); int *q = (int*) calloc ((N+1)*2, sizeof(int)); for (int i = 1; i < Graf->pocetUzlu; i++) { if (howManyNeighbours(i, Graf) == 2 && doesItHaveSameNumberOfNeighboursNeighbours(i, Graf)) { int *possibleSokety = bfs(q, visited, smer, i, Graf, 0, 0); int *resultik = checkResultik(i, smer, possibleSokety, Graf); if (resultik == NULL) { for (int z = 0; z < Graf->pocetUzlu; z++) { visited[z] = 0; smer[z] = 0; } } else { for (int i = 1; i < Graf->pocetUzlu && i < 101; i++) { if (resultik[i] != 0) { printf("%d ", resultik[i]); } } printf("\n"); return 0; } } } return 0; }
package alg; import java.util.ArrayList; /** * @author Kešu */ public class Node implements Comparable{ ArrayList<Node> connections = new ArrayList<Node>(); int number; int depth = 0; boolean socket = false; public Node(int number){ this.number = number; } public void addConnection(Node node){ this.connections.add(node); } public int getNumberOfConnections(){ return this.connections.size(); } @Override public int compareTo(Object o) { return this.number - ((Node)o).number; } } package alg; import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; /** * @author Kešu */ public class Main { //private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); private static InputReader reader = new InputReader(System.in); //static private ArrayList<Node> nodes; static private Node[] nodes; static private ArrayList<Node> sockets; //static private ArrayList<Node> visited; static private byte[] visits; static boolean first = true; static private int numberOfConnections; static private int numberOfNodes; static private int numberOfSockets; //S = C + 2 - N public static void main(String[] args) { //int[] info = readLine(); try{ numberOfNodes = reader.nextInt(); numberOfConnections = reader.nextInt(); }catch(IOException ex){ System.err.println(Arrays.toString(ex.getStackTrace())); } numberOfSockets = numberOfConnections + 2 - numberOfNodes; nodes = new Node[numberOfNodes]; sockets = new ArrayList<>(numberOfSockets); readGraph(); //Collections.sort(nodes); iterateGraph(); Collections.sort(sockets); for(int i = 0; i < sockets.size()-1 && i < 100-1; i++){ System.out.print(sockets.get(i).number+" "); } System.out.print(sockets.get(Math.min(99,sockets.size()-1)).number+"\n"); } private static ArrayList<Node> layer; private static void iterateGraph(){ for(Node n: nodes){ if(n.getNumberOfConnections() != 2) continue; //visited = new ArrayList<>(); visits = new byte[numberOfNodes]; layer = new ArrayList<>(); sockets = new ArrayList<>(numberOfSockets); layer.addAll(n.connections); sockets.add(n); n.socket = true; visits[n.number-1]+=1; int depth = 1; while(true){ if(!compareSubtrees(layer,depth)) break; if(sockets.size() == numberOfSockets) return; depth+=1; layer = loadNextLayer(layer); if(layer.size()%2 != 0) break; } } } private static boolean compareSubtrees(ArrayList<Node> nodes, int depth){ //HashMap<Integer,Integer> degrees = new HashMap<Integer,Integer>(); for(Node n: nodes){ //Node n = nodes.get(i); int conn = n.getNumberOfConnections(); int num = n.number; /*if(degrees.containsKey(conn)) degrees.replace(conn, degrees.get(conn)+1); else degrees.put(conn, 1);*/ //if(!visited.contains(n)){ if(visits[num-1] == 0){ n.socket = false; n.depth = depth; //visited.add(n); visits[num-1]+=1; } else if(n.depth == depth){ if(conn == 2){ sockets.add(n); n.socket = true; //visited.remove(n); visits[num-1]+=1; } else return false; } else return false; } /*for(int val: degrees.values()){ if(val%2 != 0) return false; }*/ return true; } private static ArrayList<Node> loadNextLayer(ArrayList<Node> layer){ ArrayList<Node> newLayer = new ArrayList<>(layer.size()); //layer.removeAll(sockets); for(Node n: layer){ if(n.socket) continue; for(Node m: n.connections){ if(visits[m.number-1] > 0) continue; newLayer.add(m); } //newLayer.addAll(n.connections); } //newLayer.removeAll(visited); //newLayer.removeAll(sockets); return newLayer; } private static void readGraph(){ //int[] info; for(int i = 0; i < numberOfConnections; i++){ //info = readLine(); try{ int value1 = reader.nextInt(); int value2 = reader.nextInt(); Node temp1, temp2; if(nodes[value1-1] != null){ temp1 = nodes[value1-1]; } else{ temp1 = new Node(value1); } if(nodes[value2-1] != null){ temp2 = nodes[value2-1]; } else{ temp2 = new Node(value2); } temp1.addConnection(temp2); temp2.addConnection(temp1); nodes[value1-1] = temp1; nodes[value2-1] = temp2; }catch(IOException ex){ System.err.println(ex.getStackTrace()); } } } /*private static int[] readLine(){ byte read = 0; char[] num = new char[7]; char[] buff = new char[1]; int[] numbers = new int[2]; try{ reader.read(buff); while(buff[0] != ' '){ num[read] = buff[0]; read++; reader.read(buff); } numbers[0] = Integer.parseInt(new String(num).trim(),10); num = new char[7]; read = 0; reader.read(buff); while(buff[0] != '\n'){ num[read] = buff[0]; read++; reader.read(buff); } numbers[1] = Integer.parseInt(new String(num).trim(),10); } catch(IOException ex){ System.err.println(Arrays.toString(ex.getStackTrace())); exit(1); } return numbers; }*/ }
package alg; public class ContextNode { public Node node; public Node parent; public ContextNode(Node node, Node parent){ this.node = node; this.parent = parent; } } package alg; import java.util.ArrayList; public class Node { ArrayList<Node> connections = new ArrayList<>(); int number; public Node(int number){ this.number = number; } public Node(int number, Node connection){ this.number = number; connections.add(connection); } public void addConnection(Node connection){ connections.add(connection); } @Override public String toString() { String str = "\n" + number + "\n=>"; for (Node conn : connections) str += " " + conn.number; return str; } } package alg; import java.io.IOException; import fastjavaio.InputReader; import java.util.LinkedList; import java.util.Queue; //import java.util.Scanner; import java.util.SortedSet; import java.util.TreeSet; public class Main { static Node[] nodes; static int[] visited; static int[] depths; static boolean[] issocket; public static void main(String[] args) throws IOException { InputReader reader = new InputReader(System.in); // Scanner scanner = new Scanner(System.in); int nodescount = reader.nextInt(); int connectionscount = reader.nextInt(); // System.err.println(nodescount + " " + connectionscount); expectedSockets = connectionscount + 2 - nodescount; nodes = new Node[nodescount + 1]; for (int i = 0; i < connectionscount; i++) { int n1 = reader.nextInt(); int n2 = reader.nextInt(); // System.err.println(n1 + " " + n2); Node node1 = nodes[n1]; Node node2 = nodes[n2]; // Node node1 = null, node2 = null; // try{ // node1 = nodes[n1]; // node2 = nodes[n2]; // System.err.println(n1 + ", " + n2 + " - OK"); // }catch (Exception ex) { // ex.printStackTrace(); // System.err.println("nodescount: " + nodescount); // System.err.println("connectionscount: " + connectionscount); // System.err.println("expectedSockets: " + expectedSockets); // System.err.println("nodes.length: " + nodes.length); // } if (node1 == null) node1 = new Node(n1); if (node2 == null) node2 = new Node(n2, node1); else node2.addConnection(node1); node1.addConnection(node2); nodes[n1] = node1; nodes[n2] = node2; } for (int i = 1; i <= nodescount; i++){ if(nodes[i].connections.size() == 2){ // System.err.println("-----------------------------\nnode " + i); visited = new int[nodescount + 1]; depths = new int[nodescount + 1]; issocket = new boolean[nodescount + 1]; sockets = new TreeSet<>(); if(BFS(nodes[i])){ finish(); return; } } } System.out.println("Sockety nenalezeny :("); } static int expectedSockets; static SortedSet<Integer> sockets; static boolean BFS(Node root){ Queue<ContextNode> queue = new LinkedList<>(); sockets.add(root.number); issocket[root.number] = true; queue.add(new ContextNode(root, null)); int depth = 1; int depthlimit = 2; int processednodes = 0; int children = 0; // visited[root.number]++; while (!queue.isEmpty()) { ContextNode node = queue.poll(); processednodes++; for (Node child : node.node.connections) { int n = child.number; if (child != node.parent && (!issocket[node.node.number] || node.parent == null)){ children += child.connections.size() - 1; if (visited[n] == 1) { if (depths[n] == depth && child.connections.size() == 2) { sockets.add(n); issocket[n] = true; // System.err.println("Socket! (" + n + ") zbývá "+(expectedSockets - sockets.size())); if (sockets.size() == expectedSockets) return true; } else return false; }else{ visited[n]++; depths[n] = depth; queue.add(new ContextNode(child, node.node)); } } } if(processednodes + 1 == depthlimit){ depth++; depthlimit = children; children = processednodes = 0; } } return false; } static void finish(){ int c = 0; String output = ""; for (int socket : sockets){ output += socket + " "; if(++c == 100) break; } System.out.println(output); // System.out.println(output.subSequence(0, output.length() - 1)); } }
package alg; import java.util.ArrayList; import java.util.List; public class Node implements Comparable<Node>{ private int value; private List<Node> neighbours = new ArrayList<Node>(); public Node(int value) { this.value = value; } public void addLink(Node node) { neighbours.add(node); } public int getNumberOfLinks() { return neighbours.size(); } public Node getLink(int index) { // Check link size return neighbours.get(index); } public List<Node> getNeighbours() { return neighbours; } public int getValue() { return value; } @Override public int compareTo(Node o) { return this.value-o.getValue(); } } package alg; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Input { int number1 = -1; int number2 = -1; BufferedReader reader; public Input() { reader = new BufferedReader(new InputStreamReader(System.in)); } public boolean readLine() throws IOException { String[] integersInString = reader.readLine().split(" "); if (integersInString[0] == null) { return false; } number1 = Integer.parseInt(integersInString[0]); number2 = Integer.parseInt(integersInString[1]); return true; } public int getNumber1() { return number1; } public int getNumber2() { return number2; } } package alg; import java.util.ArrayList; import java.util.List; public class Graph { List<Node> graph = new ArrayList<Node>(); List<Node> possibleSockets = new ArrayList<Node>(); private int size; // Number of nodes in graph private int connections; public Graph(int size, int connections) { this.size = size; this.connections = connections; ///// [1] for(int i = 0; i < size; i++) { graph.add(new Node(i+1)); } } public void createConnection(int node1, int node2) { /*if (graph.get(node1-1).getNumberOfLinks() == 1) { possibleSockets.add(graph.get(node1-1)); } if (graph.get(node2-1).getNumberOfLinks() == 1) { possibleSockets.add(graph.get(node2-1)); } ///// [2] if (graph.get(node1-1).getNumberOfLinks() == 2) { possibleSockets.remove(graph.get(node1-1)); } if (graph.get(node2-1).getNumberOfLinks() == 2) { possibleSockets.remove(graph.get(node2-1)); }*/ graph.get(node1-1).addLink(graph.get(node2-1)); graph.get(node2-1).addLink(graph.get(node1-1)); } public Node getNode(int node) { return graph.get(node); } public int getSize() { return size; } public int getConnections() { return connections; } } package alg; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Logic { Graph graph; List<Integer> sockets = new ArrayList<Integer>(); public Logic(Graph graph) { this.graph = graph; for (Node n: graph.graph) { if (n.getNumberOfLinks() == 2) { graph.possibleSockets.add(n); } } Collections.sort(graph.possibleSockets); } public boolean isSolution(Node node) { // The main logic of the whole project Node leftChild = node.getLink(0); Node rightChild = node.getLink(1); if (leftChild.getNumberOfLinks() != rightChild.getNumberOfLinks()) { return false; } //sockets.add(node.getValue()); List<Node> leftQueue = new ArrayList<Node>(); List<Node> rightQueue = new ArrayList<Node>(); leftQueue.add(leftChild); rightQueue.add(rightChild); boolean[] visited = new boolean[graph.getSize() + 1]; visited[node.getValue()] = true; while(!leftQueue.isEmpty() && !rightQueue.isEmpty()) { int[] frequency = new int[graph.getSize() + 1]; int asymmetry = 0; Collections.sort(leftQueue); Collections.sort(rightQueue); int l = 0; int r = 0; int leftSize = leftQueue.size(); int rightSize = rightQueue.size(); while(l < leftSize || r < rightSize) { if (l < leftSize && r < rightSize) { if ((leftQueue.get(l).getValue() == rightQueue.get(r).getValue()) && (leftQueue.get(l).getNumberOfLinks() == 2)) { sockets.add(node.getValue()); if ((leftSize == 1) && (rightSize == 1)) { sockets.add(leftQueue.get(l).getValue()); } //sockets.add(leftQueue.get(l).getValue()); return true; /*visited[leftQueue.get(l).getValue()] = true; l++; r++; continue;*/ } } if (l < leftSize) { if (!visited[leftQueue.get(l).getValue()]) { for (Node n : leftQueue.get(l).getNeighbours()) { if (!visited[n.getValue()]) { frequency[n.getNumberOfLinks()]++; if (frequency[n.getNumberOfLinks()] == 1) { asymmetry++; } leftQueue.add(n); } } } } if (r < rightSize) { if (!visited[rightQueue.get(r).getValue()]) { for (Node n : rightQueue.get(r).getNeighbours()) { if (!visited[n.getValue()]) { frequency[n.getNumberOfLinks()]--; if (frequency[n.getNumberOfLinks()] == 0) { asymmetry--; } rightQueue.add(n); } } } } if (l < leftSize) { visited[leftQueue.get(l).getValue()] = true; } if (r < rightSize) { visited[rightQueue.get(r).getValue()] = true; } if ((l < leftSize && (leftQueue.get(l).getValue() < rightQueue.get(r).getValue())) || (r >= rightSize)) { l++; } else if ((r < rightSize && (leftQueue.get(l).getValue() > rightQueue.get(r).getValue())) || (l >= leftSize)) { r++; } } if (asymmetry != 0) { //sockets.clear(); return false; } for (int k = 0; k < leftSize; k++) { leftQueue.remove(0); } for (int k = 0; k < rightSize; k++) { rightQueue.remove(0); } } if ( leftQueue.isEmpty() && rightQueue.isEmpty() ) { return true; } else { //sockets.clear(); return false; } } public void findSolution() { /*for (int i = 0; i < graph.getSize(); i++) { if (graph.getNode(i).getNumberOfLinks() == 2) { if (isSolution(graph.getNode(i))) { if (!sockets.isEmpty()) { int socketsSize; if (sockets.size() > 100) { socketsSize = 100; } else { socketsSize = sockets.size(); } Collections.sort(sockets); System.out.print(sockets.get(0)); for (int j = 1; j < socketsSize; j++) { System.out.print(" " + sockets.get(j)); } System.out.println(); break; } } } }*/ ///// [3] Collections.sort(graph.possibleSockets); if (graph.getSize() == graph.getConnections()) { isSolution(graph.possibleSockets.get(0)); System.out.println(sockets.get(0) + " " + sockets.get(1)); } else { int counter = 0; for (Node n: graph.possibleSockets) { if (isSolution(n)) { counter++; } if (counter == 100) { break; } } System.out.print(sockets.get(0)); for(int i = 1; i < sockets.size(); i++) { System.out.print(" " + sockets.get(i)); } System.out.println(); } } } package alg; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { Input input = new Input(); input.readLine(); Graph graph = new Graph(input.getNumber1(), input.getNumber2()); for (int i = 0; i < graph.getConnections(); i++) { if (input.readLine()) { graph.createConnection(input.getNumber1(), input.getNumber2()); } else { System.out.println("alg.Input Stream error"); System.exit(0); } } Logic logic = new Logic(graph); logic.findSolution(); } }
from sys import stdin class Graph: def __init__(self, edge, nodes, edges): self.nodes = nodes self.edges = edges self.noc = [0 for x in range(nodes)] self.data = [[] for x in range(nodes)] for i in range(int(len(edge) / 2)): e1 = int(edge[i * 2]) - 1 e2 = int(edge[i * 2 + 1]) - 1 self.noc[e1] += 1 self.noc[e2] += 1 self.data[e1].append(e2) self.data[e2].append(e1) def print_data(self, data=None): if not data: data = self.data n = 0 for line in data: print ("{:5} - " + ("{:5}" * len(line))).format(*([n] + line)) n += 1 def _num_of_con(self): return (self.edges + 2) - self.nodes def _get_candidates(self): candidates = [x for x in range(self.nodes) if self.noc[x] == 2] res = [] for one in candidates: neighbors = self.data[one] if self.noc[neighbors[0]] == self.noc[neighbors[1]]: res.append(one) return res def BFS_tree_mirror(self, starting): result = [starting] node_data = [float("inf")] * self.nodes l1 = [self.data[starting][0]] l2 = [self.data[starting][1]] node_data[starting] = 0 node_data[l1[0]] = 0 node_data[l2[0]] = 0 i = 0 while(len(result) < self._num_of_con()): i += 1 tl1 = set() for item in l1: for node in self.data[item]: if node_data[node] < i - 2: return None elif node_data[node] > i: tl1.add(node) node_data[node] = i tl2 = set() for item in l2: for node in self.data[item]: if node_data[node] < i - 2: return None elif node_data[node] > i: tl2.add(node) node_data[node] = i elif node_data[node] == i: result.append(node) tl1.remove(node) if len(l1) != len(l2): return None l1 = list(tl1) l2 = list(tl2) return result nodes, edges = [int(x) for x in stdin.readline().split()] edgelist = [] # for line in stdin.readlines(): edgelist = " ".join(stdin.readlines()).split() # edgelist.append([int(x) - 1 for x in line.split()]) g = Graph(edgelist, nodes, edges) cand = g._get_candidates() cand.sort() for candidate in cand: res = g.BFS_tree_mirror(candidate) if res: res.sort() res = res[0:100] print(" ".join([str(x + 1) for x in res])) break