I have tried disjoint set method to detect cycle. But it shows TLE all the time in judge(6). The same problem exists when i use the dfs method to detect cycle.
Here is the dfs method:
import java.io.*;
import java.util.*;
class Main{
static boolean[] visited;
public static boolean isTree(int[][] graph,boolean[] visited,int src){
visited[src]=true;
boolean truth=true;
for(int i=1;i<graph[src].length;i++){
if(graph[src][i]==1){
if(i==src)
return false;
if(!visited[i])
truth=truth && isTree(graph,visited,i);
else
return false;
//System.out.print(src+" "+i+" "+truth+" ");
}
}
//System.out.println();
return truth;
}
public static void main(String[] args)throws Exception{
//BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
//BufferedReader br=new BufferedReader(new FileReader("input.txt"));
Scanner sc=new Scanner(System.in);
String line;
String[] ar;
int i,j,k,N,M,u,v;
int[][] graph;
ar=sc.nextLine().split(" ");
N=Integer.parseInt(ar[0]);
M=Integer.parseInt(ar[1]);
graph=new int[N+1][N+1];
i=1;
while(i<M+1){
ar=sc.nextLine().split(" ");
u=Integer.parseInt(ar[0]);
v=Integer.parseInt(ar[1]);
graph[u][v]=1;
i++;
}
visited=new boolean[N+1];
if(Main.isTree(graph,visited,1)){
//System.out.println("YES");
for(i=1;i<visited.length;i++){
if(visited[i]==false){
System.out.println("NO");
break;
}
}
if(i==visited.length)
System.out.println("YES");
}
else
System.out.println("NO");
}
}
Please help!!! I am a novice.
