Advertisement
Ne-Biolog

Untitled

Jan 26th, 2018
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.71 KB | None | 0 0
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4.  
  5. // (づ°ω°)づミe★゜・。。・゜゜・。。・゜☆゜・。。・゜゜・。。・゜
  6.  
  7. namespace TASK
  8. {
  9. class MainClass
  10. {
  11. public static List<int> FindCycle(int[] parent, int u, int v)
  12. {
  13. List<int> Cycle = new List<int>();
  14. while (u != v)
  15. {
  16. Cycle.Add(u);
  17. u = parent[u];
  18. }
  19. Cycle.Add(v);
  20. Cycle.Reverse();
  21. return Cycle;
  22. }
  23.  
  24. public static List<int> dfs(List<int>[] Graph, int[] used, int [] parent , int v , List<int> z)
  25. {
  26. if (z.Count > 0)
  27. return z;
  28. used[v] = 1;
  29. for (int i = 0; i < Graph[v].Count; ++i)
  30. {
  31. if (z.Count > 0)
  32. return z;
  33. int to = Graph[v][i];
  34. parent[to] = v;
  35. if (used[to] == 1)
  36. {
  37. z = FindCycle(parent, v, to);
  38. return z;
  39. }
  40. if (used[to] == 0)
  41. dfs(Graph, used, parent, to, z);
  42. }
  43. used[v] = 2;
  44. return z;
  45. }
  46.  
  47. public static int check(List<int>[] Graph, int[] used, int v)
  48. {
  49. int ans = 0;
  50. used[v] = 1;
  51. for (int i = 0; i < Graph[v].Count; ++i)
  52. {
  53. int to = Graph[v][i];
  54. if (used[to] == 1)
  55. {
  56. return Math.Max(ans, 1);
  57. }
  58. if (used[to] == 0)
  59. check(Graph, used, to);
  60. }
  61. used[v] = 2;
  62. return ans;
  63. }
  64.  
  65. public static void Main(string[] args)
  66. {
  67. int N = Reader.NextInt();
  68. int m = Reader.NextInt();
  69. List<int>[] Graph = new List<int>[N + 1];
  70. for (int i = 0; i < m; ++i)
  71. {
  72. int from = Reader.NextInt();
  73. int to = Reader.NextInt();
  74. if (Graph[from] == null)
  75. Graph[from] = new List<int>();
  76. if (Graph[to] == null)
  77. Graph[to] = new List<int>();
  78. Graph[from].Add(to);
  79. }
  80. bool flag = false;
  81. int[] used = new int[N + 1];
  82. int[] parent = new int[N + 1];
  83. for (int i = 0; i <= N; ++i)
  84. parent[i] = i;
  85. List <int> Cycle = new List<int>();
  86. for (int i = 1; i <= N; ++i)
  87. {
  88. if (used[i] == 0 && flag == false)
  89. {
  90. List<int> z = new List<int>();
  91. List<int> res = dfs(Graph, used, parent, i , z);
  92. if (res.Count != 0)
  93. {
  94. Cycle = res;
  95. flag = true;
  96. }
  97. }
  98. }
  99. if (!flag)
  100. {
  101. Console.WriteLine("YES");
  102. }
  103. else
  104. {
  105. int ans = 0;
  106. for (int i = 1; i <= Cycle.Count; ++i)
  107. {
  108. int x = Cycle[i - 1], y = Cycle[i];
  109. Graph[x].Remove(y);
  110. for (int j = 1; j <= N; ++j)
  111. used[i] = 0;
  112. bool ok = false;
  113. for (int j = 1; j <= N; ++j)
  114. {
  115. if (used[j] == 0 && ok == false)
  116. {
  117. int T = check(Graph, used, j);
  118. ans = Math.Max(ans, T);
  119. }
  120. }
  121. Graph[x].Add(y);
  122. }
  123. Console.WriteLine(ans == 1 ? "YES" : "NO");
  124. }
  125.  
  126. }
  127.  
  128. class Reader
  129. {
  130. public static int NextInt()
  131. {
  132. int cnt = 0, sign = 1;
  133. char ch = Convert.ToChar(Console.Read());
  134. while (!(ch >= '0' && ch <= '9') && ch != '-')
  135. ch = Convert.ToChar(Console.Read());
  136. if (ch == '-')
  137. {
  138. sign = -1;
  139. ch = Convert.ToChar(Console.Read());
  140. }
  141. while (ch >= '0' && ch <= '9')
  142. {
  143. int t = Convert.ToInt32(ch);
  144. cnt = cnt * 10 + ch - '0';
  145. ch = Convert.ToChar(Console.Read());
  146. }
  147. return cnt * sign;
  148. }
  149. public static long NextLong()
  150. {
  151. long cnt = 0, sign = 1;
  152. char ch = Convert.ToChar(Console.Read());
  153. while (!(ch >= '0' && ch <= '9') && ch != '-')
  154. ch = Convert.ToChar(Console.Read());
  155. if (ch == '-')
  156. {
  157. sign = -1;
  158. ch = Convert.ToChar(Console.Read());
  159. }
  160. while (ch >= '0' && ch <= '9')
  161. {
  162. long t = Convert.ToInt64(ch);
  163. cnt = cnt * 10 + ch - '0';
  164. ch = Convert.ToChar(Console.Read());
  165. }
  166. return cnt * sign;
  167. }
  168. }
  169. }
  170. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement