#include<iostream> #include<cstdio> #include<string> #include<vector> #include<map> #include<algorithm> using namespace std; class DS{ private: vector<int>parent,rank,setSize; int numSets; public: DS(int n) { numSets=n; parent.assign(n,0); rank.assign(n,0); setSize.assign(n,1); for (int i=0;i<n;i++) parent[i]=i; } int findParent(int i) { return parent[i]==i?i:parent[i]=findParent(parent[i]); } bool isSame(int i,int j) { return findParent(i)==findParent(j);} void unionSet(int x,int y) { int xRoot=findParent(x); int yRoot=findParent(y); if (xRoot==yRoot) return; if (rank[xRoot]>rank[yRoot]) { setSize[xRoot]+=setSize[yRoot]; parent[yRoot]=xRoot; } else { setSize[yRoot]+=setSize[xRoot]; parent[xRoot]=yRoot; if (rank[xRoot]==rank[yRoot]) rank[yRoot]++; } numSets--; } int numDisjointSet(){ return numSets; } int SizeOfSet(int i) { return setSize[findParent(i)]; } }; map<string,int>m; int main() { int testcases; scanf("%d",&testcases); while (testcases--) { int friendships; scanf("%d",&friendships); DS u(friendships*2); m.clear(); string s1,s2; int indexing=0; while (friendships--) { cin>>s1>>s2; if (!m.count(s1)) m[s1]=indexing++; if (!m.count(s2)) m[s2]=indexing++; u.unionSet(m[s1],m[s2]); printf("%d\n",u.SizeOfSet(m[s1])); } } return 0; }
Friday, September 23, 2016
UVA 11503 - Virtual Friends Solution
Unknown
Studying at Shahjalal University of Science and Technology, Sylhet.
Subscribe to:
Post Comments (Atom)
Testing comment box
ReplyDeleteMore easier solution :
ReplyDelete#include
#define MAX 100010
#define ll long long
using namespace std;
ll parent[MAX],group[MAX];
ll find_friend(ll n)
{
if(parent[n]==n)return n;
return (parent[n]=find_friend(parent[n]));
}
int unio_set(ll u,ll v)
{
ll U=find_friend(u);
ll V=find_friend(v);
if(U!=V)
{
parent[V]=U;
group[U]+=group[V];
}
return group[U];
}
int main()
{
char s1[22], s2[22];
ll T, node;
map m;
scanf("%lld", &T);
while(T--)
{
ll a=0;
ll cnt=0;
scanf("%lld", &node);
for(ll i=0; i " << 1 << endl;
parent[a]=a;
group[a]=1;
m[s1]=a++;
}
if(m.find(s2)==m.end())
{
//cout << "m2 - > " << 1 << endl;
parent[a]=a;
group[a]=1;
m[s2]=a++;
}
ll x = m[s1];
ll y = m[s2];
ll res = unio_set(x,y);
printf("%lld\n", res);
}
m.clear();
}
return 0;
}