Python 3: solution without flow algorithm

def crabGraphs(n, t, graph):
    cnn={x:[] for x in range(1,n+1)}
    for u,v in graph:
        cnn[u].append(v)
        cnn[v].append(u)
    nodes=set()
    for u in sorted(cnn, key=lambda s:len(cnn[s]),reverse=True):
        if u not in nodes and len(cnn[u])>=t:
            nodes.add(u)
    for u in sorted(cnn, key=lambda s:len(cnn[s]),reverse=True):
        feetofu=0
        for v in cnn[u]:
            if v not in nodes and feetofu<t:
                nodes.add(v)
                feetofu+=1
    return len(nodes)

can anybody explain how for this (first test in testcase #1) 50 4 4 46 44 46 10 20 16 43 21 the answer will be 7??? Obviously there is no crabs with 4 legs in this graph.

c++ soution

include

include

include

using std::vector; using std::deque; using Matrix=vector>;

int residual_capacity(const Matrix &cap, const Matrix &flow, int from, int to){ if(cap[from][to]) return cap[from][to]-flow[from][to]; else if(cap[to][from]) return flow[to][from]; else return 0; }

vector residual_path(const Matrix &cap, const Matrix &flow){ const int no_parent=-2, unvisited=-1; const int source=cap.size()-2,sink=source+1; vector parent(sink+1,unvisited); parent[source]=no_parent; deque bfs; vector path; bfs.push_back(source); while(!bfs.empty()){ int i=bfs.front(); bfs.pop_front(); for(int j=0;j

Matrix max_flow(const Matrix &cap){ const int source=cap.size()-2,sink=source+1; Matrix flow(sink+1,vector(sink+1,0)); auto path=residual_path(cap,flow); while(!path.empty()){ int min_cap=cap.size(); for(int j=0;j

int solve(Matrix &cap){ const int source=cap.size()-2,nnode=source/2; auto flow=max_flow(cap); int total=0; for(int i=0;i

void input_case(){ int nnode=0, nfeet=0, nedge=0; std::cin >> nnode >> nfeet >> nedge; const int source=2*nnode, sink=source+1; Matrix cap(sink+1,vector(sink+1,0)); while(nedge--){ int i=0, j=0; std::cin >> i >> j; --i; --j; cap[2*i][2*j+1]=1; cap[2*j][2*i+1]=1; ++cap[source][2*i]; ++cap[source][2*j]; } for(int i=0;infeet){ cap[source][2*i]=nfeet; } } std::cout << solve(cap) << '\n'; }

int main(){ int ncase=0; std::cin >> ncase; while(ncase--) input_case(); }

It took me a while to get my head around this one, even with all the helpful links. I was able to implement a solution that passes all tests. Now I am wondering what the solution would look like if crabs had to have exactly N number of legs (instead of at most). Any ideas?

1. Find terminal nodes (leaf nodes are they called?) - They will be the nodes that have only one adjascent node.
2. Find the direct parents of these nodes
3. Out of point 2 find those direct parents which have more than T leaf nodes
4. Substract from n (total number of vertices) the count of all standalone nodes, plus the sum of the excess leaf nodes from point 3.

Ready.