Мы дали разные пары чисел. Теперь нам нужно создать цепочку, которая, если какой-либо элемент из 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
Вы можете представить числа в виде вершин графа. Пары будут ребрами. Теперь все, что вам нужно сделать, это запустить BFS для подсчета подключенных частей.
Алгоритм поиска союза очень эффективно решить эту проблему (ваш пример не строит цепочки, только множества)