Friday, September 23, 2016

UVA 11503 - Virtual Friends Solution

Unknown
#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;
}

Unknown

Studying at Shahjalal University of Science and Technology, Sylhet.

2 comments:

  1. More easier solution :

    #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;
    }

    ReplyDelete

Coprights @ 2016,