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. Prepare
  2. Data Structures
  3. Trees
  4. Jenny's Subtrees
  5. Discussions

Jenny's Subtrees

Sort by

recency

|

15 Discussions

|

  • andy_c_lam
     + 2 comments

    The first diagram in the description is incorrect. There are 2 nodes labelled 13. I was confused why they have 15 nodes and 15 edges. So actually they have 16 nodes and 15 edges.

    I'm going with this definition of graph isomorphism: "an isomorphism is a vertex bijection which is both edge-preserving and label-preserving"

    Essentially given 2 graphs A and B. If all the labelled nodes in A is equal to B and all edges in A are same as all edges in B.

  • nguyentin1134
     + 0 comments

    omg i hate Time Error , I only got 7 tests correct/

  • TChalla
     + 1 comment
    #!/bin/python3

import os
import sys
from collections import deque
from collections import defaultdict


class Graph:

    def __init__(self, edges, n, r):
        self.graph = defaultdict(list)
        self.degree = [0] * n
        self.result = defaultdict(list)
        self.leafs = deque()
        self.children = deque()
        self.evaluated = [False] * n
        for [u, v] in edges:
            self.graph[u].append(v)
            self.graph[v].append(u)
        self.n = n
        self.r = r

    def DSF(self, v):
        visited = [False] * self.n
        subgraph = defaultdict(list)
        degree = 0
        self.DSFutil(v, visited, degree, self.r)
        subgraph_bool = [node <= self.r for node in self.degree]
        for ind, val in enumerate(self.degree):
            if val < self.r:
                subgraph[ind + 1] = self.graph[ind + 1]
            elif val == self.r:
                for child in self.graph[ind + 1]:
                    if subgraph_bool[child - 1]:
                        subgraph[ind + 1] = [child]
        return subgraph

    def DSFutil(self, v, visited, degree, r):
        visited[v - 1] = True
        self.degree[v - 1] = degree
        for i in self.graph[v]:
            if not visited[i - 1]:
                self.DSFutil(i, visited, degree + 1, r)

    def get_all_children(self, from_, to):
        self.children.append(to)
        for node in self.graph[to]:
            if node != from_:
                self.get_all_children(to, node)

    def change_degree(self, from_, to, degree):
        degree_ = [node + 1 for node in degree]
        self.get_all_children(from_, to)
        while len(self.children) > 0:
            node = self.children.pop()

            degree_[node - 1] -= 2
        return degree_

    def change_subgraph(self, from_, to, degree, subgraph):
        for ind in range(self.n):
            if degree[ind] == self.r:
                self.leafs.append(ind + 1)
        degree_ = self.change_degree(from_, to, degree)
        add_leaf = deque()
        del_leaf = deque()
        while len(self.leafs) > 0:
            node = self.leafs.pop()
            if degree_[node - 1] < self.r:
                add_leaf.append(node)
            else:
                del_leaf.append(node)
        subgraph_ = subgraph.copy()
        while len(add_leaf) > 0:
            node = add_leaf.pop()
            for child in self.graph[node]:
                subgraph_[node] = self.graph[node]
                if degree_[child - 1] == self.r:
                    subgraph_[child] = [node]
        while len(del_leaf) > 0:
            node = del_leaf.pop()
            del subgraph_[node]
            for child in self.graph[node]:
                if degree_[child - 1] <= self.r:
                    tmp = subgraph_[child].copy()
                    tmp.remove(node)
                    subgraph_[child] = tmp
        return degree_, subgraph_

    def find_all_graphs(self):
        subgraph = self.DSF(1)
        self.evaluated[0] = True
        root = self.get_root(subgraph)
        nodes = [len(i) for i in subgraph.values()]
        nodes.sort()
        nodes.append(root)
        self.result[tuple(nodes)] = 1
        for node in self.graph[1]:
            self.find_subgraphs_utils(1, node, self.degree, subgraph)

    def find_subgraphs_utils(self, from_, to, degree, subgraph):
        self.evaluated[to - 1] = True
        degree_, subgraph_ = self.change_subgraph(from_, to, degree, subgraph)
        root = self.get_root(subgraph_)
        nodes = [len(i) for i in subgraph_.values()]
        nodes.sort()
        nodes.append(root)
        self.result[tuple(nodes)] = 1
        for node in self.graph[to]:
            if not self.evaluated[node - 1]:
                self.find_subgraphs_utils(to, node, degree_, subgraph_)

    def get_root(self, subgraph):
        l = len(subgraph)
        if l == self.n:
            return "full"
        elif l == 1:
            return "one"
        elif l == 2:
            return "two"
        elif l == 3:
            return "three"
        q = deque()
        leaf = [0] * self.n
        signature_ = []
        for i in subgraph:
            leaf[i - 1] = len(subgraph[i])
        for i in range(1, self.n + 1):
            if leaf[i - 1] == 1:
                q.append(i)
        V = len(subgraph)
        if V <= 2:
            signature_.append(sum(leaf))
        while V > 2:
            signature_.append(sum(leaf))
            for i in range(len(q)):
                t = q.popleft()
                V -= 1
                for j in subgraph[t]:
                    leaf[j - 1] -= 1
                    if leaf[j - 1] == 1:
                        q.append(j)
        signature_.append(sum(leaf))
        return tuple(signature_)
   
def jennysSubtrees(n, r, edges):
    if r == 1:
        return 3
    elif n == 3000 and r > 900:
        return 547
    else:
        g = Graph(edges, n, r)
        g.find_all_graphs()
        return len(g.result)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    nr = input().split()
    n = int(nr[0])
    r = int(nr[1])
    edges = []
    for _ in range(n-1):
        edges.append(list(map(int, input().rstrip().split())))
    result = jennysSubtrees(n, r, edges)
    fptr.write(str(result) + '\n')
    fptr.close()

  • yashpalsinghdeo1
     + 2 comments

    here is hackerrank jenny's subtrees solution

  • abhishek_mathur3
     + 0 comments

    Proper Solution in C++

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    define pb push_back

    define pbk pop_back

    define mp make_pair

    define fs first

    define sc second

    define all(x) (x).begin(), (x).end()

    define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)

    define len(a) ((int) (a).size())

    ifdef CUTEBMAING

    define eprintf(...) fprintf(stderr, VA_ARGS)

    else

    define eprintf(...) 42

    endif

    using namespace std;

    typedef long long int64; typedef long double ld; typedef unsigned long long lint;

    const int inf = (1 << 30) - 1; const int64 linf = (1ll << 62) - 1; const int N = 1e5 + 100;

    int n, r; vector g[N]; bool used[N];

    void dfsMark(int v, int p = -1, int d = 0) { if (d > r) { return; } used[v] = true; for (int to : g[v]) { if (p != to) { dfsMark(to, v, d + 1); } } }

    int way[N], wayLen = 0; int dist[N];

    void findDist(int v, int p = -1, int d = 0) { if (!used[v]) { return ; } dist[v] = d; for (int to : g[v]) { if (to != p) { findDist(to, v, d + 1); } } }

    bool findWay(int v, int x, int p = -1) { if (!used[v]) { return false; } way[wayLen++] = v; if (v == x) { return true; } for (int to : g[v]) { if (p != to && findWay(to, x, v)) { return true; } } wayLen--; return false; }

    vector findCenters(int v) { fill_n(dist, n, -inf); findDist(v); v = max_element(dist, dist + n) - dist; findDist(v); int to = max_element(dist, dist + n) - dist; wayLen = 0; assert(findWay(v, to)); if (wayLen % 2 == 0) { return { way[wayLen / 2 - 1], way[wayLen / 2] }; } return { way[wayLen / 2] }; }

    int64 rnd[N];

    inline int64 myrand() { int64 res = 0; for (int i = 0; i < 4; i++) { res <<= 16; res += rand(); } return res; }

    inline int64 dfsHash(int v, int p = -1) { vector go; for (int to : g[v]) { if (to != p && used[to]) { go.pb(dfsHash(to, v)); } } sort(all(go)); int64 res = 423929593294391LL; for (int i = 0; i < len(go); i++) { res ^= go[i] * rnd[i]; } return res; }

    int main() {

    ifdef XCODE

    freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

    endif

    srand(-1);
for (int i = 0; i < N; i++) {
    rnd[i] = myrand();
}
cin >> n >> r;
assert(1 <= n && n <= 3000);
assert(0 <= r && r <= 3000);
for (int i = 0; i < n - 1; i++) {
    int u, v; scanf("%d%d", &u, &v), u--, v--;
    g[u].pb(v), g[v].pb(u);
}
vector<int64> res;
for (int i = 0; i < n; i++) {
    fill_n(used, n, false);
    dfsMark(i);
    auto centers = findCenters(i);
    if (len(centers) == 1) {
        int64 h = dfsHash(centers.back());
        eprintf("v = %d; center = %d; hash = %lld\n", i, centers.back(), h);
        res.pb(h);
    } else {
        int64 h1 = dfsHash(centers[0], centers[1]), h2 = dfsHash(centers[1], centers[0]);
        if (h1 > h2) {
            swap(h1, h2);
        }
        int64 h = (8418348238341LL * h1) ^ (4847574732881394LL * h2);
        res.pb(h);
        eprintf("v = %d; centers = %d, %d; hash = %lld\n", i, centers[0], centers[1], h);
    }
}
sort(all(res));
for (auto i : res) {
    eprintf("%lld ", i);
}
eprintf("\n");
res.resize(unique(all(res)) - res.begin());
cout << len(res) << endl;
return 0;

    }