Advertisement
Ne-Biolog

Untitled

Jan 26th, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.63 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. Graph[from].Add(to);
  77. }
  78. bool flag = false;
  79. int[] used = new int[N + 1];
  80. int[] parent = new int[N + 1];
  81. for (int i = 0; i <= N; ++i)
  82. parent[i] = i;
  83. List <int> Cycle = new List<int>();
  84. for (int i = 1; i <= N; ++i)
  85. {
  86. if (used[i] == 0 && flag == false)
  87. {
  88. List<int> z = new List<int>();
  89. List<int> res = dfs(Graph, used, parent, i , z);
  90. if (res.Count != 0)
  91. {
  92. Cycle = res;
  93. flag = true;
  94. }
  95. }
  96. }
  97. if (!flag)
  98. {
  99. Console.WriteLine("YES");
  100. }
  101. else
  102. {
  103. int ans = 0;
  104. for (int i = 1; i <= Cycle.Count; ++i)
  105. {
  106. int x = Cycle[i - 1], y = Cycle[i];
  107. Graph[x].Remove(y);
  108. for (int j = 1; j <= N; ++j)
  109. used[i] = 0;
  110. bool ok = false;
  111. for (int j = 1; j <= N; ++j)
  112. {
  113. if (used[j] == 0 && ok == false)
  114. {
  115. int T = check(Graph, used, j);
  116. ans = Math.Max(ans, T);
  117. }
  118. }
  119. Graph[x].Add(y);
  120. }
  121. Console.WriteLine(ans == 1 ? "YES" : "NO");
  122. }
  123.  
  124. }
  125.  
  126. class Reader
  127. {
  128. public static int NextInt()
  129. {
  130. int cnt = 0, sign = 1;
  131. char ch = Convert.ToChar(Console.Read());
  132. while (!(ch >= '0' && ch <= '9') && ch != '-')
  133. ch = Convert.ToChar(Console.Read());
  134. if (ch == '-')
  135. {
  136. sign = -1;
  137. ch = Convert.ToChar(Console.Read());
  138. }
  139. while (ch >= '0' && ch <= '9')
  140. {
  141. int t = Convert.ToInt32(ch);
  142. cnt = cnt * 10 + ch - '0';
  143. ch = Convert.ToChar(Console.Read());
  144. }
  145. return cnt * sign;
  146. }
  147. public static long NextLong()
  148. {
  149. long cnt = 0, sign = 1;
  150. char ch = Convert.ToChar(Console.Read());
  151. while (!(ch >= '0' && ch <= '9') && ch != '-')
  152. ch = Convert.ToChar(Console.Read());
  153. if (ch == '-')
  154. {
  155. sign = -1;
  156. ch = Convert.ToChar(Console.Read());
  157. }
  158. while (ch >= '0' && ch <= '9')
  159. {
  160. long t = Convert.ToInt64(ch);
  161. cnt = cnt * 10 + ch - '0';
  162. ch = Convert.ToChar(Console.Read());
  163. }
  164. return cnt * sign;
  165. }
  166. }
  167. }
  168. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement