Все пары чисел создают все возможные цепочки

Мы дали разные пары чисел. Теперь нам нужно создать цепочку, которая, если какой-либо элемент из pair1 равен какому-либо элементу из pair2, тогда они принадлежат одному и тому же набору.

Пример:-

данные пары:

(0,1)
(2,3)
(5,4)
(3,5)
(7,6)
(8,7)

Так что все готово

{0,1}, {2,3,4,5}, {6,7,8}

Как мы можем достичь этого. Я не задумывался об этом. Любая помощь будет оценена.

Решение
Код C
#включают

#define SIZE 100100

int visited[SIZE];struct adjListNode{
int dest;
struct adjListNode* next;
};

struct adjList{
struct adjListNode* head;
};

struct Graph{
int V;
struct adjList* array;
};

struct adjListNode* newAdjListNode(int dest){
struct adjListNode* newNode = (struct adjListNode*)malloc(sizeof(struct adjListNode));
newNode->dest = dest;
newNode->next = NULL;

return newNode;
}struct Graph* createGraph(int V){
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;

graph->array = (struct adjList*)malloc(V * sizeof(struct adjList));

int i;
for(i = 0; i < V; i++){
graph->array[i].head = NULL;
}

return graph;
}

void addEdge(struct Graph* graph, int src, int dest){
struct adjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;

newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}

void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->V; ++v)
{
struct adjListNode* pCrawl = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}

void DFS(struct Graph* graph, int v){
if(visited[v] == 0){
visited[v] = 1;
printf("%d --> ", v);
struct adjListNode *pCrawl = graph->array[v].head;
while(pCrawl){
if(visited[pCrawl->dest] == 0){
DFS(graph, pCrawl->dest);
}
pCrawl = pCrawl->next;
}
}
}int main(void) {
int V = 5, I, src, dest, i, count = 0;
scanf("%d %d", &V, &I);
memset(visited, 0, SIZE);
struct Graph* graph = createGraph(V);
while(I--){
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}

for(i = 0; i < V; i++){
if(visited[i] == 0){
count++;
DFS(graph, i);
printf("\n");
}
}
// print the adjacency list representation of the above graph
printGraph(graph);
printf("Countries :- %d", count);

return 0;
}

вход

10 8
0 1
2 3
1 4
5 6
7 8
9 7
1 7
3 5

Выход

SET :: 0 --> 1 --> 7 --> 9 --> 8 --> 4 -->
SET :: 2 --> 3 --> 5 --> 6 -->

Adjacency list of vertex 0
head -> 1

Adjacency list of vertex 1
head -> 7-> 4-> 0

Adjacency list of vertex 2
head -> 3

Adjacency list of vertex 3
head -> 5-> 2

Adjacency list of vertex 4
head -> 1

Adjacency list of vertex 5
head -> 3-> 6

Adjacency list of vertex 6
head -> 5

Adjacency list of vertex 7
head -> 1-> 9-> 8

Adjacency list of vertex 8
head -> 7

Adjacency list of vertex 9
head -> 7
Sets :- 2

0

Решение

Вы можете представить числа в виде вершин графа. Пары будут ребрами. Теперь все, что вам нужно сделать, это запустить BFS для подсчета подключенных частей.

0

Другие решения

Алгоритм поиска союза очень эффективно решить эту проблему (ваш пример не строит цепочки, только множества)

0