(SPOJ) Rodovia - Solution
Link to the problem: http://br.spoj.com/problems/RODOVI13/
The solution below used Kosaraju's algorithm to solve this problem.
import java.io.*;
import java.util.*;
class Main {
public HashMap<Integer, ArrayList<Integer>> adjList;
public HashMap<Integer, ArrayList<Integer>> adjListReverse;
public HashSet<Integer> visited;
public Deque<Integer> stack;
public void dfsReverse(int node) {
if (visited.contains(node)) {
return;
}
visited.add(node);
ArrayList<Integer> reachNodes = adjListReverse.get(node);
for (int i = 0; i < reachNodes.size(); i++) {
node = reachNodes.get(i);
dfsReverse(node);
}
}
public void dfs(int node) {
if (visited.contains(node)) {
return;
}
visited.add(node);
int oldNode = node;
ArrayList<Integer> reachNodes = adjList.get(node);
for (int i = 0; i < reachNodes.size(); i++) {
node = reachNodes.get(i);
dfs(node);
}
stack.push(oldNode);
}
public void process() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String line = br.readLine();
int numCities = Integer.parseInt(line);
adjList = new HashMap<>();
adjListReverse = new HashMap<>();
for (int i = 1; i <= numCities; i++) {
adjList.put(i, new ArrayList<Integer>());
adjListReverse.put(i, new ArrayList<Integer>());
}
for (int i = 0; i < numCities; i++) {
line = br.readLine();
String[] s = line.split("\\s");
int c1 = Integer.parseInt(s[0]);
int c2 = Integer.parseInt(s[1]);
adjList.get(c1).add(c2);
adjListReverse.get(c2).add(c1);
}
stack = new ArrayDeque();
visited = new HashSet<>();
for (int i = 1; i <= numCities; i++) {
if (visited.contains(i)) {
continue;
}
dfs(i);
}
int count = 0;
int size = stack.size();
visited = new HashSet<>();
for (int i = 0; i < size; i++) {
int elem = stack.pop();
if (visited.contains(elem)) {
continue;
}
dfsReverse(elem);
count++;
}
if (count == 1) {
bw.write("S\n");
}
else {
bw.write("N\n");
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
The solution below used Kosaraju's algorithm to solve this problem.
import java.io.*;
import java.util.*;
class Main {
public HashMap<Integer, ArrayList<Integer>> adjList;
public HashMap<Integer, ArrayList<Integer>> adjListReverse;
public HashSet<Integer> visited;
public Deque<Integer> stack;
public void dfsReverse(int node) {
if (visited.contains(node)) {
return;
}
visited.add(node);
ArrayList<Integer> reachNodes = adjListReverse.get(node);
for (int i = 0; i < reachNodes.size(); i++) {
node = reachNodes.get(i);
dfsReverse(node);
}
}
public void dfs(int node) {
if (visited.contains(node)) {
return;
}
visited.add(node);
int oldNode = node;
ArrayList<Integer> reachNodes = adjList.get(node);
for (int i = 0; i < reachNodes.size(); i++) {
node = reachNodes.get(i);
dfs(node);
}
stack.push(oldNode);
}
public void process() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String line = br.readLine();
int numCities = Integer.parseInt(line);
adjList = new HashMap<>();
adjListReverse = new HashMap<>();
for (int i = 1; i <= numCities; i++) {
adjList.put(i, new ArrayList<Integer>());
adjListReverse.put(i, new ArrayList<Integer>());
}
for (int i = 0; i < numCities; i++) {
line = br.readLine();
String[] s = line.split("\\s");
int c1 = Integer.parseInt(s[0]);
int c2 = Integer.parseInt(s[1]);
adjList.get(c1).add(c2);
adjListReverse.get(c2).add(c1);
}
stack = new ArrayDeque();
visited = new HashSet<>();
for (int i = 1; i <= numCities; i++) {
if (visited.contains(i)) {
continue;
}
dfs(i);
}
int count = 0;
int size = stack.size();
visited = new HashSet<>();
for (int i = 0; i < size; i++) {
int elem = stack.pop();
if (visited.contains(elem)) {
continue;
}
dfsReverse(elem);
count++;
}
if (count == 1) {
bw.write("S\n");
}
else {
bw.write("N\n");
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
Comments
Post a Comment