Codeforces: 263D - Cycle in Graph, Run time error Test 12

[doctorzlai]

http://www.codeforces.com/problemset/problem/263/D

DFS, I think the error is caused by recursion, too many levels of recursion calls. stack overflow.
but so far I can't think of any better approach.

Code: Select all

#!/usr/bin/env python

n, m, k = map(int, raw_input().split())

e = [[] for _ in xrange(n + 1)]
for i in xrange(m):
    x, y = map(int, raw_input().split())
    e[x].append(y)
    e[y].append(x)
    
vis = [False] * (n + 1)

def ok(x, y):
    global e
    for i in e[x]:
        if y == i:
            return True
    return False

def search(ans, x, n, k):
    global vis, e
    if len(ans) > k:
        if ok(ans[0], x) or ok(x, ans[0]):
            return ans
    for i in e[x]:
        if not vis[i]:
            vis[i] = True
            ans.append(i)
            s = search(ans, i, n, k)
            if len(s) > k:
                return s
            ans.pop(len(ans) - 1)
            vis[i] = False
    return []

for i in xrange(1, n + 1):
    vis = [False] * (n + 1)
    vis[i] = True
    s = search([i], i, n, k)
    vis[i] = False
    if len(s) > k:
        print len(s)
        print ' '.join(map(str, s))        
        break

Any helps here?

[doctorzlai]

ok.. after a second thought, i found out it is unnecessary to check again and again the nodes on the same path (if visited before). This will cause time limit if a length is particular very long.
if the current node has been visited before (the path containing the node), just ignore it and carry on.

Maybe a BFS approach is also feasible here?

[doctorzlai]

I've seen other accepted solutions and none of them are in Python... the accepted code are mostly written in C++ or Pascal for this problem.

maybe this cannot be solved using Python?

I will try later.

[doctorlai]

Code: Select all

#!/usr/bin/env python

n, m, k = map(int, raw_input().split())

# build the graph
e = [[] for _ in xrange(n + 1)]
for i in xrange(m):
    x, y = map(int, raw_input().split())
    e[x].append(y)
    e[y].append(x)

# find the answer?
done = False

d = [0] * (n + 1)
# ans array
ans = [0] * (n + 2)

def dfs(v, x):
    global done, ans, k, e, d
    if done:
        return
    if d[v] > 0:
        if x - d[v] > k:
            # count
            print x - d[v]
            print ' '.join(map(str, ans[d[v]:x]))
            done = True
        return
    # node v appears at depth x
    d[v] = x
    for i in e[v]:
        ans[x + 1] = i
        dfs(i, x + 1)

for i in xrange(1, n + 1):
    if d[i] == 0:
        ans[1] = i
        dfs(i, 1)

Re-write, but still got Runtime error on test 17 (maybe Time Limit ?)

[doctorlai]

I will rewrite the python code in other programming languages later and see how it goes.

[doctorlai]

I will rewrite the python code in other programming languages later and see how it goes.

I rewrite the above Python code in Java and it got accepted.

Time Memory
515 ms 16100 KB

[dfy]

I have to admit I'm rather unfamiliar with the python syntax, so I don't really understand your approach yet (I will be rereading it tomorrow). But it seems to me that you're not making a lot of use of the fact that the minimal degree of the graph is k. That should contribute more to the problem than a bounds check.

[doctorlai]

I have to admit I'm rather unfamiliar with the python syntax, so I don't really understand your approach yet (I will be rereading it tomorrow). But it seems to me that you're not making a lot of use of the fact that the minimal degree of the graph is k. That should contribute more to the problem than a bounds check.

Yes, thanks, you are right... I didn't notice this before..
but how exactly can we speed up base on this fact?

[dfy]

I'm not really sure yet. There are a few nice graph theory theorems about cycles in such graphs, but I'll have to trace through them to see how constructive they are.

By the way, my current python solution (not algorithmically great, it's a randomized trial/error) gets runtime errors too. I'm wondering whether that's actually a problem with their python configuration? Can't be stack size, it's not recursive. I'll retry in Java or C++ later.

[doctorlai]

I'm not really sure yet. There are a few nice graph theory theorems about cycles in such graphs, but I'll have to trace through them to see how constructive they are.

By the way, my current python solution (not algorithmically great, it's a randomized trial/error) gets runtime errors too. I'm wondering whether that's actually a problem with their python configuration? Can't be stack size, it's not recursive. I'll retry in Java or C++ later.

Actually, the Python is not very good for online contests. Aside TLE, Runtime Error seems rather quite frequent, probably because it uses more memory per structure than C/C++.