===== Sockets detection =====
==== Přehled ====
[[https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=videocard|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
#include
#include
#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
#include
#include
#include
#include
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; iadjLists[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; fadjLists[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
#include
#include
#include
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 connections = new ArrayList();
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 nodes;
static private Node[] nodes;
static private ArrayList sockets;
//static private ArrayList 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 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 nodes, int depth){
//HashMap degrees = new HashMap();
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 loadNextLayer(ArrayList layer){
ArrayList 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 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 sockets;
static boolean BFS(Node root){
Queue 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{
private int value;
private List neighbours = new ArrayList();
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 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 graph = new ArrayList();
List possibleSockets = new ArrayList();
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 sockets = new ArrayList();
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 leftQueue = new ArrayList();
List rightQueue = new ArrayList();
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