Moderator: Board moderators

I used standart algo for searching bridges, but got a WA.

http://ideone.com/qbu9F

Code: Select all
import java.io.*;
import java.util.*;

public class Main {
static int n;
static Scanner sc = new Scanner(System.in);
static PrintWriter pw = new PrintWriter(System.out);
static int[][] a;
static int[][] ans;
static int ansCount;

static boolean[] used;
static int timer;
static int[] tin;
static int[] tup;

static void read() throws IOException {
n = sc.nextInt();
a = new int[n][];
ansCount = 0;
ans = new int[n][2];
for(int l = 0; l < n; l++) {
int i = sc.nextInt();
String s = sc.next();
int count = Integer.parseInt(s.substring(1, s.length() - 1));
a[i] = new int[count];
for(int k = 0; k < count; k++)
a[i][k] = sc.nextInt();
}

}

static void out() {
Arrays.sort(ans, 0, ansCount , new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
if(o1[0] > o2[0])
return 1;
else
if(o1[0] < o2[0])
return -1;
if(o1[1] > o2[1])
return 1;
else
return -1;
}
});

for(int i = 0; i < ansCount; i++) {
pw.println(ans[i][0] + " - " + ans[i][1] );
}
}

static void bridge(int a, int b) {
ans[ansCount][0] = Math.min(a, b);
ans[ansCount][1] = Math.max(a, b);
ansCount++;
}

static void solve() {
timer = 0;
used = new boolean[n];
tin = new int[n];
tup = new int[n];
for(int i = 0; i < n; i++)
if(!used[i])
dfs(i, -1);
}

static void dfs(int v, int p) {
used[v] = true;
tin[v] = tup[v] = timer++;
for(int i = 0; i < a[v].length; i++) {
int to = a[v][i];
if(to == p)
continue;
if(used[to])
tup[v] = Math.min(tup[v], tin[to]);
else {
dfs(to, v);
tup[v] = Math.min(tup[v], tup[to]);
if(tin[v] < tup[to])
bridge(v, to);
}

}

}

public static void main(String[] args) throws IOException {
try
{
while(true) {
solve();
out();
if(sc.hasNext())
pw.println();
else
return;
}

}
finally {
pw.close();
}

}

}
shtorm941
New poster

Posts: 7
Joined: Sat Mar 10, 2012 5:46 pm

Check whether you have done two things:
1. Print a blank line after every test cases.
2. first element of two links are similar then sort them ascending orderly to their second element.
ducse1527
New poster

Posts: 1
Joined: Tue Jun 19, 2012 9:01 am

ducse1527 wrote:Check whether you have done two things:
1. Print a blank line after every test cases.
2. first element of two links are similar then sort them ascending orderly to their second element.

1. I print a blank line. Look at this: http://ideone.com/qbu9F
2.Also I sort edges by first element and then (if first elements are equals) sort by second element.
Code: Select all
new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
if(o1[0] > o2[0])
return 1;
else
if(o1[0] < o2[0])
return -1;
if(o1[1] > o2[1])
return 1;
else
return -1;
}
})
shtorm941
New poster

Posts: 7
Joined: Sat Mar 10, 2012 5:46 pm

1. Print a blank line after every test cases - including the last one.
brianfry713
Guru

Posts: 1751
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

brianfry713 wrote:1. Print a blank line after every test cases - including the last one.

Thanks, it helped me.
shtorm941
New poster

Posts: 7
Joined: Sat Mar 10, 2012 5:46 pm