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) —
loading...
Last Post: Solve the Knight Tour in Python (Breadth First Search Algorithm)
Next Post: Codeforces: A. Colorful Stones (Simplified Edition)