SHARE
TWEET

graph connectivity

NAbdulla Jul 7th, 2015 (edited) 344 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /****************************************************************************************
  2.    *  Md. Abdulla Al Mamun (Nayon)
  3.    *  ID: 1306001
  4.    *  Session: 2013-2014
  5.    *  Department of Computer Science and Engineering
  6.    *  Begum Rokeya University, Rangpur (BRUR)
  7.    *
  8.    *  Project Name:                     Graph Connectivity
  9.    *  File Created on:          Monday, 2015-07-06-00.50.13
  10.    *  Current File:                     D:\My Codes\C and C++\Code-Blocks Projects\Graph Connectivity\main.cpp
  11.    *  Language:                         English (U.S.)
  12.    *  Encoding:                         windows-1252
  13. *****************************************************************************************/
  14. #include <iostream>
  15. #include <cstdio>
  16. #include <string>
  17. #include <cstring>
  18. #include <algorithm>
  19. #include <vector>
  20. #include <cmath>
  21.  
  22. using namespace std;
  23.  
  24. struct graph{
  25.     int parent;
  26.     int depth;
  27. };
  28.  
  29. graph nodes[30];
  30.  
  31. void ini(int n)
  32. {
  33.     int i;
  34.     for(i = 1; i <= n; i++){
  35.         nodes[i].parent = i;
  36.         nodes[i].depth = 0;
  37.     }
  38. }
  39.  
  40. int find_repre(int n)
  41. {
  42.     if(nodes[n].parent != n){
  43.         nodes[n].parent = find_repre(nodes[n].parent);
  44.     }
  45.     return nodes[n].parent;
  46. }
  47.  
  48. void make_friend(int a, int b)
  49. {
  50.     int x = find_repre(a);
  51.     int y = find_repre(b);
  52.     if(x != y){
  53.         if(nodes[x].depth < nodes[y].depth)nodes[x].parent = y;
  54.         else if(nodes[x].depth > nodes[y].depth)nodes[y].parent = x;
  55.         else{
  56.             nodes[y].parent = x;
  57.             nodes[x].depth++;
  58.         }
  59.     }
  60. }
  61.  
  62. int main()
  63. {
  64.     //freopen("in.txt", "r", stdin);
  65.     int t, i, ans, n;
  66.     char str[5], s, e;
  67.  
  68.     scanf("%d", &t);
  69.     getchar();
  70.     getchar();
  71.     bool f = false;
  72.     while(t--){
  73.         if(f)printf("\n");
  74.         f = true;
  75.         gets(str);
  76.         n = str[0] - 'A'+1;
  77.         ini(n);
  78.         while((gets(str)) && (strlen(str) != 0)){
  79.             s = str[0];
  80.             e = str[1];
  81.             make_friend(s-'A'+1, e-'A'+1);
  82.         }
  83.         ans = 0;
  84.         for(i = 1; i <= n; i++){
  85.             if(nodes[i].parent == i)ans++;
  86.         }
  87.         printf("%d\n", ans);
  88.     }
  89.     return 0;
  90. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top