We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Friend Circle Queries
  2. Discussions

Friend Circle Queries

Sort by

recency

|

91 Discussions

|

  • dderugin
     + 0 comments

    ugly but working Java solution:

    Map<Integer, Set<Integer>> index = new HashMap<>();
        int[] steps = new int[queries.length];

        int max = 0;
        int i = 0;
        for (int[] query : queries) {
            int a = query[0];
            int b = query[1];

            Set<Integer> leftGraph = index.get(a);
            Set<Integer> rightGraph = index.get(b);

            if(leftGraph == null && rightGraph == null) {
                Set<Integer> n = new HashSet<>();
                n.add(a);
                n.add(b);
                index.put(a, n);
                index.put(b, n);

                max = Math.max(max, n.size());
            } else if(leftGraph == null) {
                rightGraph.add(a);
                index.put(a, rightGraph);

                max = Math.max(max, rightGraph.size());
            } else if(rightGraph == null) {
                leftGraph.add(b);
                index.put(b, leftGraph);

                max = Math.max(max, leftGraph.size());
            } else {
                if(leftGraph == rightGraph) {
                    leftGraph.add(a);
                    leftGraph.add(b);

                    index.put(a, leftGraph);
                    index.put(b, leftGraph);

                    max = Math.max(max, leftGraph.size());
                } else {
                    // merge
                    if(leftGraph.size() > rightGraph.size()) {
                        leftGraph.addAll(rightGraph);
                        index.put(b, leftGraph);
                        for (Integer v : rightGraph) {
                            index.put(v, leftGraph);
                        }
                        max = Math.max(max, leftGraph.size());
                    } else {
                        rightGraph.addAll(leftGraph);
                        index.put(b, rightGraph);
                        for (Integer v : leftGraph) {
                            index.put(v, rightGraph);
                        }
                        max = Math.max(max, rightGraph.size());
                    }
                }
            }

            steps[i] = max;
            i++;
        }
        return steps;

  • yiqiang1996
     + 0 comments

    javascript union-find, using Map instead of Array. easy to understand:

    function maxCircle(queries) {

    let parentMap = new Map()
let sizeMap = new Map()
let maxGroup = 1


function find(p){
    if(parentMap.has(p)){
        while(p!==parentMap.get(p)){
            parentMap.set(p, parentMap.get(parentMap.get(p)))
            p = parentMap.get(p)
        }  
    }else{
        parentMap.set(p, p)   
    }

    return p
}

function union(p, q){
    let rootP = find(p)
    let rootQ = find(q)
    if(!sizeMap.has(rootP)){
        sizeMap.set(rootP, 1)
    }

    if(!sizeMap.has(rootQ)){
        sizeMap.set(rootQ, 1)
    }

    if(rootP===rootQ){
        return maxGroup
    }

    let groupSize = sizeMap.get(rootP)+sizeMap.get(rootQ)

    if(sizeMap.get(rootP)<sizeMap.get(rootQ)){
        parentMap.set(rootP, rootQ)
        sizeMap.set(rootQ, groupSize)  
    }else{
        parentMap.set(rootQ, rootP)
        sizeMap.set(rootP, groupSize)
    }
    maxGroup = Math.max(maxGroup, groupSize)
    return maxGroup
}

let res = []
for(let [p,q] of queries){
    res.push(union(p,q))
}

return res

    }

  • dehaka
     + 0 comments

    modified to prevent memory issues from creating a vector of size 10^9

    class disjoint_set {
public:
    vector<int> parent = { 0 }, size = { 0 };
    disjoint_set(int n) {
        for (int i = 1; i <= n; i++) {
            parent.push_back(i);
            size.push_back(1);
        }
    }
    int find(int x) {
        if (x != parent[x]) parent[x] = find(parent[x]);
        return parent[x];
    }
    void Union(int x, int y) {
        int xRep = find(x), yRep = find(y);
        if (xRep == yRep) return;
        if (size[xRep] <= size[yRep]) {
            parent[xRep] = yRep;
            size[yRep] = size[yRep] + size[xRep];
        }
        else {
            parent[yRep] = xRep;
            size[xRep] = size[xRep] + size[yRep];
        }
    }
};

vector<int> maxCircle(const vector<int>& people, const vector<vector<int>>& queries) {
    disjoint_set world(people.size());
    vector<int> result;
    int largest = 1;
    for (auto q : queries) {
        auto it0 = lower_bound(people.begin(), people.end(), q[0]);
        auto it1 = lower_bound(people.begin(), people.end(), q[1]);
        int p0 = it0 - people.begin() + 1, p1 = it1 - people.begin() + 1;
        world.Union(p0, p1);
        int x = world.find(p0), y = world.find(p1);
        largest = max({largest, world.size[x], world.size[y]});
        result.push_back(largest);
    }
    return result;
}

int main()
{
    int q, k, l = 0;
    vector<vector<int>> queries;
    set<int> S;
    vector<int> people;
    cin >> q;
    for (int i=1; i <= q; ++i) {
        cin >> k >> l;
        S.insert(k);
        S.insert(l);
        queries.push_back({k, l});
    }
    people.assign(S.begin(), S.end());
    auto X = maxCircle(people, queries);
    for (int x : X) cout << x << '\n';
}

  • anthonyabunassar
     + 0 comments

    Has anyone solved this, using disjoint sets, in Go or Python? My Go benchmark using Test 10 takes 2 seconds, yet that test fails when I submit my code.

    My Python code is also correct, but runs out of time on Test 10.

    I'd hate having to rewrite this in C++.

  • amourayuba
     + 0 comments

    My Disjoint Set solution. Just a small modification to a dictionnary for the size and parents instead of an array.

    # ACUTAL SOLUTION WITH DISJOINT SET 
class DisjointSet:
    def __init__(self):
        self.parent = {}
        self.size = {}

    def find(self, i):
        if i not in self.parent:
            self.parent[i] = i
            self.size[i] = 1
            return i
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def unionBySize(self, i, j):
        irep = self.find(i)
        jrep = self.find(j)
        if irep == jrep:
            return
        isize = self.size[irep]
        jsize = self.size[jrep]

        if isize < jsize:
            self.parent[irep] = jrep
            self.size[jrep] += self.size[irep]
        else:
            self.parent[jrep] = irep
            self.size[irep] += self.size[jrep]


def maxCircle(queries):
    dset = DisjointSet()
    maxlen = 0
    maxlens = []
    for query in queries:
        f1, f2 = query
        dset.unionBySize(f1, f2)
        maxlen = max(maxlen, dset.size[dset.find(f1)])
        maxlens.append(maxlen)
    return maxlens