SHARE
TWEET

Untitled

a guest Sep 18th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3.  
  4. //struct Edge {
  5. //  int first;
  6. //  int second;
  7. //};
  8.  
  9. void dfs(size_t** graph, size_t vertex, size_t* colors, size_t color, size_t vertices_count);
  10.  
  11. int main() {
  12.   FILE* file = fopen("input", "r");
  13.   size_t N;
  14.   fscanf(file, "%lu", &N);
  15.   size_t** graph = (size_t**)calloc(N + 1, sizeof(size_t*));
  16.  
  17.   for (size_t i = 0; i < N + 1; ++i) {
  18.     graph[i] = (size_t*)calloc(N + 1, sizeof(size_t));
  19.   }
  20.  
  21.   size_t left, right;
  22.   while(fscanf(file, "%lu %lu", &left, &right) != EOF) {
  23.     graph[left][right] = 1;
  24.     graph[right][left] = 1;
  25.   }
  26.  
  27.   size_t* colors = (size_t*)calloc(N + 1, sizeof(size_t));
  28.  
  29.   size_t color = 1;
  30.   for (size_t i = 0; i < N + 1; ++i) {
  31.     if (colors[i] == 0) {
  32.       colors[i] = color;
  33.       dfs(graph, i, colors, color, N + 1);
  34.       ++color;
  35.     }
  36.   }
  37.  
  38.   for (size_t i = 1; i < color; ++i) {
  39.     for (size_t j = 0; j < N + 1; ++j) {
  40.       if (colors[j] == i) {
  41.         std::cout << j << ' ';
  42.         fflush(stdin);
  43.       }
  44.     }
  45.     std::cout << std::endl;
  46.   }
  47.  
  48.   return 0;
  49. }
  50.  
  51. void dfs(size_t** graph, size_t vertex, size_t* colors, size_t color, size_t vertices_count) {
  52.   for (size_t i = 0; i < vertices_count; ++i) {
  53.     if (graph[vertex][i]) {
  54.       if (colors[i] == 0) {
  55.         colors[i] = color;
  56.         dfs(graph, i, colors, color, vertices_count);
  57.       }
  58.     }
  59.   }
  60. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top