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 BufferedReader br;
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() {
pw.println(ansCount + " critical links");
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) {
read();
solve();
out();
if(sc.hasNext())
pw.println();
else
return;
}
}
finally {
pw.close();
}
}
}