Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #define SIZE 100
- struct edge{
- int u, v;
- } E[SIZE];
- struct disjointset
- {
- int parent;
- int size;
- int rank;
- } S[SIZE];
- void get_edge_list(int m)
- {
- int x, y;
- for(int i = 0; i< m; i++)
- {
- scanf("%d %d", &x, &y);
- E[i].u = x;
- E[i].v= y;
- }
- }
- void initialize_set(int n)
- {
- for(int i = 0; i<n; i++)
- {
- S[i].rank = 0;
- S[i].parent = i;
- S[i].size = 1;
- }
- }
- int find_parent(int u)
- {
- if(S[u].parent == u)
- {
- return u;
- }
- else
- return find_parent(S[u].parent);
- }
- void unions(int u, int v)
- {
- if(S[u].rank > S[v].rank)
- {
- S[v].parent = u;
- S[u].size++;
- }
- else if(S[u].rank < S[v].rank)
- {
- S[u].parent = v;
- S[v].size++;
- }
- else{
- S[v].parent = u;
- S[u].rank ++;
- S[u].size++;
- }
- }
- void process_graph(int n, int m)
- {
- int u, v;
- initialize_set(n);
- for(int i= 0; i<m; i++)
- {
- u = find_parent(E[i].u);
- v = find_parent(E[i].v);
- if ( u!= v)
- unions(u, v);
- }
- }
- int component_count(int n)
- {
- int count = 0;
- for(int i = 0; i< n; i++)
- {
- if(S[i].parent == i)
- count++;
- }
- return count;
- }
- int largest_component_size(int n)
- {
- int maz = 0;
- for(int i = 0; i<n; i++)
- {
- if(maz < S[i].size)
- maz = S[i].size;
- }
- return maz;
- }
- void parentNodes(int v)
- {
- if(S[v].parent == v)
- return;
- else{
- printf("%d ", S[v].parent);
- return parentNodes(S[v].parent);
- }
- }
- void component_nodes(int n, int v)
- {
- for(int i = 0; i<n; i++)
- {
- if(S[v].parent == S[i].parent)
- {
- printf("%d ", i);
- }
- }
- }
- int main()
- {
- freopen("input.txt", "r", stdin);
- int n,m;
- scanf("%d %d", &n, &m);
- get_edge_list(m);
- process_graph(n, m);
- for(int i = 0; i< n; i++)
- {
- printf("%d have rank %d and parent %d and size %d\n", i, S[i].rank, S[i].parent, S[i].size);
- }
- printf("Total component %d\n", component_count(n));
- printf("Largest component size is %d\n", largest_component_size(n));
- parentNodes(2);
- printf("\n");
- component_nodes(n, 3);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement