• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?