Hi ,
i m getting error can u find the error in code for following problem??
We will use the following (standard) definitions from graph theory. Let V be
a nonempty and finite set, its elements being called vertices (or nodes).
Let E be a subset of the Cartesian product V×V, its elements being called
edges. Then G=(V,E) is called a directed graph.
Let n be a positive integer, and let p=(e1,...,en) be a sequence of
length nof edges
ei∈ E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1). Then
p is called a path from vertex v1 to vertex vn+1 in G and we say that
vn+1is reachable from
v1, writing (v1→vn+1).
Here are some new definitions. A node v in a graph G=(V,E) is called a sink,
if for every node w in G that is reachable from v, v is also reachable from
w. The bottom of a graph is the subset of all nodes that are sinks, i.e.,
bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of
certain graphs.
Input Specification
The input contains several test cases, each of which corresponds to a
directed graph G. Each test case starts with an integer number v, denoting
the number of vertices of G=(V,E), where the vertices will be identified by
the integer numbers in the set V={1,...,v}. You may assume that 1<=v<=5000.
That is followed by a non-negative integer e and, thereafter, e pairs of
vertex identifiers v1,w1,...,ve,we with the meaning that (vi,wi)∈E. There
are no edges other than specified by these pairs. The last test case is
followed by a zero.
Output Specification
For each test case output the bottom of the specified graph on a single
line. To this end, print the numbers of all nodes that are sinks in sorted
order separated by a single space character. If the bottom is empty, print
an empty line.
Sample Input
3 3
1 3 2 3 3 1
2 1
1 2
0
Sample Output
1 3
2
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public int[][] matrix;
public int n;
public static void main(String args[]){
try{
BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
String s= br.readLine();
while(!s.trim().equals("0"))
{
s= s.trim();
String [] dim = s.split("[ ]+");
Main graph = new Main();
graph.n= Integer.parseInt(dim[0]);
int edgesCount = Integer.parseInt(dim[1]);
if(edgesCount ==0){
for(int i=0; i<graph.n ; ++i)
System.out.print((i+1)+" ");
System.out.print("\n");
s= br.readLine();
continue;
}
graph.matrix = new int[graph.n][graph.n];
for(int i=0; i<graph.n ;++i){
for(int j=0; j<graph.n; ++j){
graph.matrix[i][j]=0;
}
}
s= br.readLine();
s= s.trim();
dim = s.split("[ ]+");
int j=0;
while(j<dim.length){
graph.matrix[Integer.parseInt(dim[j])-1][Integer.parseInt(dim[j+1])-1] = 1;
j+=2;
}
int n = graph.n;
int [][] temp = new int [graph.n][graph.n];
for(int i=0 ; i<graph.n ;++i){
copy(graph.matrix,temp,graph.n);
graph.processGraph(temp,i);
}
for(int i=0; i<graph.n ;++i){
for(j=0; j<graph.n; ++j){
if(graph.matrix[i][j]==1 ){
if(graph.matrix[j][i]==1)
;
else
break;
}
}
if(j==n){
System.out.print((i+1) + " ");
}
/*else
System.out.println("not founf " + i);*/
}
System.out.print("\n");
s= br.readLine();
}
}
catch(Exception e ){
System.out.println(e);
}
}
public void processGraph(int [][] temp,int val){
boolean tmp ;
for(int i=0 ;i<n ;++i)
for(int j=0; j<n ; j++){
tmp = (temp[i][j]==1) || ((temp[i][val]==1) &&
(temp[val][j]==1));
matrix[i][j] = tmp?1:0;
}
}
public static void copy(int[][] graph , int [][] tmp , int n){
for(int i=0 ; i<n;++i)
for(int j=0;j<n;j++)
tmp[i][j] = graph[i][j];
}
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
