fork download
copy 
  1. import java.io.InputStreamReader;
  2. import java.io.IOException;
  3. import java.io.BufferedReader;
  4. import java.io.OutputStream;
  5. import java.io.PrintWriter;
  6. import java.util.StringTokenizer;
  7. import java.io.InputStream;
  8.  
  9. /**
  10.  * Built using CHelper plug-in
  11.  * Actual solution is at the top
  12.  * @author Rubanenko
  13.  */
  14. public class Main {
  15. 	public static void main(String[] args) {
  16. 		InputStream inputStream = System.in;
  17. 		OutputStream outputStream = System.out;
  18. 		InputReader in = new InputReader(inputStream);
  19. 		PrintWriter out = new PrintWriter(outputStream);
  20. 		Dag solver = new Dag();
  21. 		solver.solve(1, in, out);
  22. 		out.close();
  23. 	}
  24. }
  25.  
  26. class Dag {
  27.  
  28.     public void solve(int testNumber, InputReader in, PrintWriter out) {
  29.         int n = in.nextInt();
  30.         boolean[][] a = new boolean[n + 1][n + 1];
  31.         boolean[][] newEdge = new boolean[n + 1][n + 1];
  32.         boolean[] used = new boolean[n + 1];
  33.         int[] outDegree = new int[n + 1];
  34.         int numberOfEdges = (n * (n - 1)) / 2;
  35.         for (int i = 0; i < n; i++) {
  36.            String s = in.next();
  37.            for (int j = 0; j < n; j++) {
  38.                a[i][j] = (s.charAt(j) == '1');
  39.                if (a[i][j]) {
  40.                    numberOfEdges--;
  41.                    outDegree[i]++;
  42.                }
  43.            }
  44.         }
  45.         out.println(numberOfEdges);
  46.         for (int i = 0; i < n; i++) {
  47.             int v = -1;
  48.             for (int j = n - 1; j >= 0; j--) {
  49.                 if (!used[j] && outDegree[j] == 0) {
  50.                     v = j;
  51.                     break;
  52.                 }
  53.             }
  54.             used[v] = true;
  55.             for (int j = 0; j < n; j++) {
  56.                 if (j != v && !a[j][v] && !used[j]) {
  57.                     newEdge[j][v] = true;
  58.                 }
  59.             }
  60.             for (int j = 0; j < n; j++) {
  61.                 if (a[j][v]) outDegree[j]--;
  62.             }
  63.         }
  64.         for (int i = 0; i < n; i++) {
  65.             for (int j = 0; j < n; j++) {
  66.                 if (newEdge[i][j]) out.println((i + 1) + " " + (j + 1));
  67.             }
  68.         }
  69.     }
  70. }
  71.  
  72. class InputReader {
  73.     private BufferedReader reader;
  74.     private StringTokenizer tokenizer;
  75.  
  76.     public InputReader(InputStream inputStream) {
  77.         reader = new BufferedReader(new InputStreamReader(inputStream));
  78.     }
  79.  
  80.     public String nextLine() {
  81.         String line = null;
  82.         try {
  83.             line = reader.readLine();
  84.         } catch (IOException e) {
  85.             throw new RuntimeException(e);
  86.         }
  87.         return line;
  88.     }
  89.  
  90.     public String next() {
  91.         while (tokenizer == null || !tokenizer.hasMoreTokens())
  92.             tokenizer = new StringTokenizer(nextLine());
  93.         return tokenizer.nextToken();
  94.     }
  95.  
  96.     public int nextInt() {
  97.         return Integer.parseInt(next());
  98.     }
  99. }
  100.  
Runtime error #stdin #stdout #stderr 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.NullPointerException
	at java.util.StringTokenizer.<init>(StringTokenizer.java:199)
	at java.util.StringTokenizer.<init>(StringTokenizer.java:236)
	at InputReader.next(Main.java:92)
	at InputReader.nextInt(Main.java:97)
	at Dag.solve(Main.java:29)
	at Main.main(Main.java:21)
https://ideone.com/4xC8xn
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!