import java.io.*; import java.util.*; /** * Use 2-sat. Build the implication graph by a creating a clause for each pair * of non-X answers for each student. Then use Tarjan's algorithm for Strongly * Connected Components to determine if there is a satisfying assignment. Then * assign all of the non-free variables. Then assign any unbound variables in * lexicgraphic order, propagating any assignments that are made. * Complexity: O(n*k^2+k^3), with a bit more care this could probably be * reduced to O(n*k^2 + k^2)=O(n*k^2), but since k has the same upper bound * as n, this is not necessary. * * @author Finn Lidbetter */ public class exam_finn { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] s = br.readLine().split(" "); int n = Integer.parseInt(s[0]); int k = Integer.parseInt(s[1]); boolean[][] adj = new boolean[2*k][2*k]; for (int i=0; i seq[q1] => ~seq[q2] <==> seq[q2] => ~seq[q1]. if (seq[q1] == 'T') { if (seq[q2] == 'T') { adj[q1][q2+k] = true; adj[q2][q1+k] = true; } else { adj[q1][q2] = true; adj[q2+k][q1+k] = true; } } else { if (seq[q2] == 'T') { adj[q1+k][q2+k] = true; adj[q2][q1] = true; } else { adj[q1+k][q2] = true; adj[q2+k][q1] = true; } } } } } Tarjan sccs = new Tarjan(adj); boolean valid = true; for (int i=0; i q = new LinkedList<>(); HashSet vis = new HashSet<>(); q.offer(sccs.id[i+k]); vis.add(sccs.id[i+k]); while (q.size()>0) { int curr = q.poll(); for (int j=0; j q = new LinkedList<>(); q.offer(src); boolean[] vis = new boolean[adj.length]; vis[src] = true; while (q.size()>0) { int curr = q.poll(); if (curr == dest) { return true; } for (int i=0; i stack = new Stack<>(); public Tarjan(boolean[][] adj) { n = adj.length; this.adj = adj; marked = new boolean[n]; id = new int[n]; low = new int[n]; for (int u = 0; u < n; u++) { if (!marked[u]) { dfs(u); } } } public void dfs(int u) { marked[u] = true; low[u] = pre++; int min = low[u]; stack.push(u); for (int v = 0; v < n; v++) { if (adj[u][v]) { if (!marked[v]) { dfs(v); } if (low[v] < min) { min = low[v]; } } } if (min < low[u]) { low[u] = min; return; } int v; do { v = stack.pop(); id[v] = count; low[v] = n; } while (v != u); count++; } }