|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <string> #include <sstream> #include <algorithm> using namespace std; struct Edge{ int source,destination,weight; }; //to keep track of parent and rank of union find struct subset{ int parent; int rank; }; bool graph[100][100]; vector<Edge> edges; subset* subsets; bool cmp(Edge a,Edge b) { return a.weight<b.weight; } int find(int node) { if(subsets[node].parent!=node) return find(subsets[node].parent); return subsets[node].parent; } void Union(int x,int y) { int xroot = find(x); int yroot = find(y); if(subsets[xroot].rank<subsets[yroot].rank) subsets[xroot].parent=yroot; else if(subsets[yroot].rank<subsets[xroot].rank) subsets[yroot].parent=xroot; else { subsets[yroot].parent=xroot; subsets[xroot].rank+=1; } } int main() { int t,no_Of_Vertices,a; int counter,kase=1; stringstream ss; string s; Edge tEdge; Edge result[100]; cin>>t; getchar(); while(t--) { cin>>no_Of_Vertices; getchar(); subsets = (subset*)malloc(sizeof(subset)*no_Of_Vertices); memset(graph,0,sizeof(graph)); edges.clear(); counter=0; for(int I=0;I<no_Of_Vertices;I++) { getline(cin,s); ss.clear(); ss<<s; for(int K=0;K<no_Of_Vertices;K++) { ss>>a; if(ss.peek()==',') ss.ignore(); if(a) { if(graph[I][K]==0) { graph[I][K]=graph[K][I]=1; tEdge.source=I; tEdge.destination=K; tEdge.weight=a; edges.push_back(tEdge); } } } } sort(edges.begin(),edges.end(),cmp); for(int I=0;I<no_Of_Vertices;I++) { subsets[I].parent=I; subsets[I].rank=0; } int i=0; while(counter<no_Of_Vertices-1) { tEdge = edges[i++]; int x = find(tEdge.source); int y = find(tEdge.destination); if(x!=y) { result[counter++]=tEdge; Union(x,y); } } cout<<"Case "<<kase++<<":\n"; char ch='A'; for(int i=0;i<counter;i++) cout<<char(ch+result[i].source)<<"-"<<char(ch+result[i].destination)<<" "<<result[i].weight<<"\n"; } return 0; } |