axy_03's blog

By axy_03, history, 4 years ago, In English

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.StringTokenizer;

public class BertownRoads { static int MAX; static ArrayList<HashSet> adj; static boolean[] visited; static int in[]; static int low[]; static int timer; static boolean hasBridge; static ArrayList<ArrayList> edgeList;

public BertownRoads(int V) {
    MAX = V + 1;
    adj = new ArrayList<HashSet<Integer>>(MAX);
    visited = new boolean[MAX];
    in = new int[MAX];
    low = new int[MAX];
    hasBridge = false;
    timer = 0;
    edgeList = new ArrayList<ArrayList<Integer>>();

    for (int i = 0; i < MAX; i++) {
       adj.add(new HashSet<Integer>());
    }
}

void dfs(int node, int par) {
    visited[node] = true;
    in[node] = timer;
    low[node] = timer;
    timer++;
    for (int child : adj.get(node)) {
       if (child == par)
         continue;

       else if (!visited[child]) {
         dfs(child, node);
         if (low[child] > in[node]) {
          hasBridge = true;
          return;
         }
         edgeList.add(new ArrayList<Integer>(Arrays.asList(node, child)));
         low[node] = Math.min(low[node], low[child]);
       }

       else {
         low[node] = Math.min(low[node], in[child]);
         if (in[node] > in[child]) {
          edgeList.add(new ArrayList<Integer>(Arrays.asList(node, child)));
         }
       }
    }
}

public static void main(String[] args) throws IOException {
    BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    int n = 0, m = 0, a, b;
    StringTokenizer st = new StringTokenizer(read.readLine(), " ");
    while (st.hasMoreTokens()) {
       n = Integer.parseInt(st.nextToken());
       m = Integer.parseInt(st.nextToken());
    }

    BertownRoads cc = new BertownRoads(n);
    for (int i = 0; i < m; i++) {
       st = new StringTokenizer(read.readLine(), " ");
       while (st.hasMoreTokens()) {
         a = Integer.parseInt(st.nextToken());
         b = Integer.parseInt(st.nextToken());
         adj.get(a).add(b);
         adj.get(b).add(a);
       }
    }

    cc.dfs(1, -1);
    if (hasBridge) {
       System.out.println(0);
    } else {
       edgeList.forEach(list -> {
         StringBuilder sb = new StringBuilder();
         list.forEach(x -> sb.append(x).append(" "));
         System.out.println(sb);
       });
    }
}

}

  • Vote: I like it
  • -30
  • Vote: I do not like it

| Write comment?