semiconnectedgraph.java

determine whether a graph is semi-connected

import java.util.*;

public class SemiConnectedGraph {

	private boolean[][] edges;
	private int N;
	
	
	public SemiConnectedGraph(boolean[][] edges) {
		this.edges = edges;
		this.N = edges.length;
	}

	public boolean IsSemiConnected() {
		boolean[][] connected = new boolean[N][N];
		for(int i = 0;i < N;i++) {
			for(int j = 0;j < N;j++) {
				connected[i][j] = edges[i][j];
			}
		}
			
		for(int i = 0;i < N;i++) {
			// traverse the graph starting from v_i, mark the nodes reached
			LinkedList<Integer> q = new LinkedList<Integer>();
			q.add(i);
			boolean[] visited = new boolean[N];
			Arrays.fill(visited, false);
			visited[i] = true;
			while(!q.isEmpty()) {
				int node = q.removeFirst();
				List<Integer> neighbors = GetNeighbors(node);
				for(int neighbor : neighbors) {
					if(!visited[neighbor]) {
						connected[i][neighbor] = true;
						q.add(neighbor);
						visited[neighbor] = true;
					}
				}
			}
		}
		
		for(int i = 0;i < N;i++) {
			for(int j = i + 1;j < N;j++) {
				if(!connected[i][j] && !connected[j][i]) {
					return false;
				}
			}
		}
			
		return true;
	}
	
	private ArrayList<Integer> GetNeighbors(int node) {
		ArrayList<Integer> ret = new ArrayList<Integer>();
		for(int j = 0;j < N;j++) {
			if(edges[node][j]) {
				ret.add(j);
			}
		}
		return ret;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		String line = in.nextLine();
		String[] parts = line.split(" ");
		assert(parts.length == 2);
		int N = Integer.parseInt(parts[0]);
		
		boolean[][] e = new boolean[N][N];	
		for(int i = 0;i < N;i++) {
			for(int j = 0;j < N;j++) {
				if(i == j) {
					e[i][j] = true;
				} else {
					e[i][j] = false;
				}
			}
		}
		while((line = in.nextLine()) != null) {
			parts = line.split(" ");
			e[Integer.parseInt(parts[0])][Integer.parseInt(parts[1])] = true;
		}
		in.close();
		
		// TODO Auto-generated method stub
//		int[][] e = new int[3][3];
//		for(int i = 0;i < 3;i++) {
//			for(int j = 0;j < 3;j++) {
//				e[i][j] = 0;
//			}
//		}
//		e[0][0] = e[1][1] = e[2][2] = e[0][1] = e[0][2] = e[2][1] = 1;
		SemiConnectedGraph g = new SemiConnectedGraph(e);
		System.out.println(g.IsSemiConnected() ? "Yes" : "No");
		
	}

}