GIven 쌍의 Number 생성 가능한 모든 체인 집합

Question

숫자의 다른 쌍을 부여했습니다. 이제 pair1의 요소가 pair2의 요소와 동일한 경우 동일한 세트에 속하는 체인을 만들어야합니다.

예 : -

주어진 쌍 :

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

그래서 모든 세트는 우리가이를 어떻게

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

있습니다. 나는 이것에 대한 생각이 없다. 어떤 도움을 주시면 감사하겠습니다.

솔루션 C 코드 사용법 #include

#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 

Answer 1

숫자를 그래프 정점으로 나타낼 수 있습니다. 쌍은 모서리입니다. 이제 bfs를 실행하여 연결된 부분을 계산하면됩니다.

Answer 2

Union-find algorithm는 시도 무엇 ...