-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathIsTree.java
More file actions
65 lines (62 loc) · 2.07 KB
/
IsTree.java
File metadata and controls
65 lines (62 loc) · 2.07 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package Tree;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
public class IsTree {
public void testing() throws IOException{
throw new IOException("");
}
static ArrayList<ArrayList<Integer>> a;
static int vis[];
static boolean cycle = false, moreCom = false;
public static void dfs(int i) {
for(int j=0;j<a.get(i).size();j++) {
int vertex = a.get(i).get(j);
if(vis[vertex] != 0 && vis[i] != vertex && vis[i] != i) {
//System.out.println("we reached here");
cycle = true;
return;
}
else if(vis[vertex] == 0) {
vis[vertex] = i;
dfs(vertex);
}
}
}
public static void main(String args[]) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s[] = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int e = Integer.parseInt(s[1]);
a = new ArrayList<>();
for(int i=0;i<n+1;i++) a.add(new ArrayList<>());
vis = new int[n+1];
for(int i=0;i<e;i++) {
String s1[] = br.readLine().split(" ");
int st = Integer.parseInt(s1[0]);
int en = Integer.parseInt(s1[1]);
a.get(st).add(en);
a.get(en).add(st);
}
int cnt = 0;
for (int i=1;i<=n;i++) {
if(cnt == 0 && vis[i] == 0) {
vis[i] = i;
cnt++;
dfs(i);
}
else if(cnt >= 1 && vis[i] == 0) {
//System.out.println("we reached here 2");
moreCom = true;
break;
}
}
//for(ArrayList<Integer> aa: a) System.out.println(aa);
//System.out.println(Arrays.toString(vis));
//if(e == 0) System.out.println("NO");
if(!moreCom && !cycle) System.out.println("YES");
else System.out.println("NO");
}
}