Codeforces: 263D Cycle of Graph

This problem is from codeforces: http://www.codeforces.com/problemset/problem/263/D

This is a graph-related problem but it took me days to get it right. First i made a mistake in using Python language, see this post and this. And, later, I realize that using Python is very difficult in solving some particular problems because it is slow in general, compared to C++ or Java. Therefore, the same algorithms implementation may pass all tests in other languages rather than Python.

Python itself is not a suitable language for online contests. Apart from TLE, Runtime Error seems rather quite frequent,  probably because it uses more memory per structure than C/C++ or Delphi/Pascal. In general, some of its operations are too slow, and you need to know the structures very well in order to choose one that has the desired asymptotic complexity.

The DFS seems a first solution. But the implementation can be quite tricky. My first solution in Python implements DFS, but not a good one. I check every node and DFS finding a cycle and exit. This gives me RE on Test 12.

#!/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):
            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

The above approach is a clear one, but not an efficient one. The list operation is costly and if the path is long, the DFS recursion can go deep which will yield stack-overflow. Meantime, the path visiting may be duplicated on nodes. For example, A->B->C->D. The node B will be visited twice and the node C will be three times and so on.

A better solution would be to use a global array d, which records the first appearance of node (depth), if the offset is bigger than k, between the current depth (of recursion) and the element d[v] we can say we have a cycle, because element v appears once before. We store the path in a global array ans.

#!/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)

This does not give a AC, instead, it gives a RE on Test 17. Rewrite this in Java yields a AC. There are faster approaches, I think, because I just realize that I might not have fully made full use of the fact that the minimal degree of the graph is k.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

import java.io.*;
import java.util.*;
 
public class codeforces
{
    static int[] d;
    static int[] a;
    static List[] g;
    static boolean done = false;
 
    static void dfs(int v, int x, int k)
    {
        if (done)
        {
            return;
        }
        if (d[v] > 0)
        {
            if (x - d[v] > k)
            {
                System.out.println(x - d[v]);
                for (int i = d[v]; i < x; i ++)
                {
                    System.out.print(a[i] + " ");
                }
                done = true;
            }
            return;
        }
        d[v] = x;
        for (int i = 0; i < g[v].size(); i ++)
        {
            int cur = (Integer)g[v].get(i);
            a[x + 1] = cur;
            dfs(cur, x + 1, k);
        }
    }
 
    public static void main(String[] args) throws IOException
    {
        BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
        String[] s = rr.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        int k = Integer.parseInt(s[2]);
        g = new ArrayList[n + 1];
        a = new int[n + 2];
        d = new int[n + 1];
        for (int i = 0; i < n + 1; i ++)
        {
            g[i] = new ArrayList();
        }
        for (int i = 0; i < m; i ++)
        {
            s = rr.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            g[x].add(y);
            g[y].add(x);
        }
        Arrays.fill(a, 0);
        Arrays.fill(d, 0);
        for (int i = 1; i < n + 1; i ++)
        {
            if (d[i] == 0)
            {
                a[1] = i;
                dfs(i, 1, k);
            }
        }
    }
}

import java.io.*;
import java.util.*;

public class codeforces
{
    static int[] d;
    static int[] a;
    static List[] g;
    static boolean done = false;

    static void dfs(int v, int x, int k)
    {
        if (done)
        {
            return;
        }
        if (d[v] > 0)
        {
            if (x - d[v] > k)
            {
                System.out.println(x - d[v]);
                for (int i = d[v]; i < x; i ++)
                {
                    System.out.print(a[i] + " ");
                }
                done = true;
            }
            return;
        }
        d[v] = x;
        for (int i = 0; i < g[v].size(); i ++)
        {
            int cur = (Integer)g[v].get(i);
            a[x + 1] = cur;
            dfs(cur, x + 1, k);
        }
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
        String[] s = rr.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        int k = Integer.parseInt(s[2]);
        g = new ArrayList[n + 1];
        a = new int[n + 2];
        d = new int[n + 1];
        for (int i = 0; i < n + 1; i ++)
        {
            g[i] = new ArrayList();
        }
        for (int i = 0; i < m; i ++)
        {
            s = rr.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            g[x].add(y);
            g[y].add(x);
        }
        Arrays.fill(a, 0);
        Arrays.fill(d, 0);
        for (int i = 1; i < n + 1; i ++)
        {
            if (d[i] == 0)
            {
                a[1] = i;
                dfs(i, 1, k);
            }
        }
    }
}

I should have abandoned Python in solving these kind of problems [see this].

** Updated ** It is possible to pass all tests using Python. Apparently my previous approach isn’t faster enough. The following Python got accepted within 560 ms.

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)

curr = 1
chain =[]
inchain = [0]*(n+1)
while True:
    if inchain[curr] == 1:
        break
    chain.append(curr)
    inchain[curr] = 1
    for i in e[curr]:
        if inchain[i] == 0:
            curr = i
            break

minindex = min(map(chain.index,e[curr]))
print len(chain) - minindex
print ' '.join(map(str,chain[minindex:]))

There is not recursion. More discussions on this problem can also be found in the forum.

–EOF (The Ultimate Computing & Technology Blog) —