Warning
This page is located in archive. Go to the latest version of this course pages.

Sockets detection

Přehled

zadání

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    

1. nejrychlejší v C/C++

#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;
}

2. nejrychlejší v C/C++

#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;
}

3. nejrychlejší v C/C++

#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;
}

1. nejrychlejší v Javě

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;
    }*/
 
}

2. nejrychlejší v Javě

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));
    }   
}

3. nejrychlejší v Javě

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();
 
    }
}

1. nejrychlejší v Pythonu

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

courses/b4b33alg/cviceni/3_sockets.txt · Last modified: 2018/09/24 15:06 (external edit)