Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections;
- using System.Collections.Generic;
- // (づ°ω°)づミe★゜・。。・゜゜・。。・゜☆゜・。。・゜゜・。。・゜
- namespace TASK
- {
- class MainClass
- {
- public static List<int> FindCycle(int[] parent, int u, int v)
- {
- List<int> Cycle = new List<int>();
- while (u != v)
- {
- Cycle.Add(u);
- u = parent[u];
- }
- Cycle.Add(v);
- Cycle.Reverse();
- return Cycle;
- }
- public static List<int> dfs(List<int>[] Graph, int[] used, int [] parent , int v , List<int> z)
- {
- if (z.Count > 0)
- return z;
- used[v] = 1;
- for (int i = 0; i < Graph[v].Count; ++i)
- {
- if (z.Count > 0)
- return z;
- int to = Graph[v][i];
- parent[to] = v;
- if (used[to] == 1)
- {
- z = FindCycle(parent, v, to);
- return z;
- }
- if (used[to] == 0)
- dfs(Graph, used, parent, to, z);
- }
- used[v] = 2;
- return z;
- }
- public static int check(List<int>[] Graph, int[] used, int v)
- {
- int ans = 0;
- used[v] = 1;
- for (int i = 0; i < Graph[v].Count; ++i)
- {
- int to = Graph[v][i];
- if (used[to] == 1)
- {
- return Math.Max(ans, 1);
- }
- if (used[to] == 0)
- check(Graph, used, to);
- }
- used[v] = 2;
- return ans;
- }
- public static void Main(string[] args)
- {
- int N = Reader.NextInt();
- int m = Reader.NextInt();
- List<int>[] Graph = new List<int>[N + 1];
- for (int i = 0; i < m; ++i)
- {
- int from = Reader.NextInt();
- int to = Reader.NextInt();
- if (Graph[from] == null)
- Graph[from] = new List<int>();
- Graph[from].Add(to);
- }
- bool flag = false;
- int[] used = new int[N + 1];
- int[] parent = new int[N + 1];
- for (int i = 0; i <= N; ++i)
- parent[i] = i;
- List <int> Cycle = new List<int>();
- for (int i = 1; i <= N; ++i)
- {
- if (used[i] == 0 && flag == false)
- {
- List<int> z = new List<int>();
- List<int> res = dfs(Graph, used, parent, i , z);
- if (res.Count != 0)
- {
- Cycle = res;
- flag = true;
- }
- }
- }
- if (!flag)
- {
- Console.WriteLine("YES");
- }
- else
- {
- int ans = 0;
- for (int i = 1; i <= Cycle.Count; ++i)
- {
- int x = Cycle[i - 1], y = Cycle[i];
- Graph[x].Remove(y);
- for (int j = 1; j <= N; ++j)
- used[i] = 0;
- bool ok = false;
- for (int j = 1; j <= N; ++j)
- {
- if (used[j] == 0 && ok == false)
- {
- int T = check(Graph, used, j);
- ans = Math.Max(ans, T);
- }
- }
- Graph[x].Add(y);
- }
- Console.WriteLine(ans == 1 ? "YES" : "NO");
- }
- }
- class Reader
- {
- public static int NextInt()
- {
- int cnt = 0, sign = 1;
- char ch = Convert.ToChar(Console.Read());
- while (!(ch >= '0' && ch <= '9') && ch != '-')
- ch = Convert.ToChar(Console.Read());
- if (ch == '-')
- {
- sign = -1;
- ch = Convert.ToChar(Console.Read());
- }
- while (ch >= '0' && ch <= '9')
- {
- int t = Convert.ToInt32(ch);
- cnt = cnt * 10 + ch - '0';
- ch = Convert.ToChar(Console.Read());
- }
- return cnt * sign;
- }
- public static long NextLong()
- {
- long cnt = 0, sign = 1;
- char ch = Convert.ToChar(Console.Read());
- while (!(ch >= '0' && ch <= '9') && ch != '-')
- ch = Convert.ToChar(Console.Read());
- if (ch == '-')
- {
- sign = -1;
- ch = Convert.ToChar(Console.Read());
- }
- while (ch >= '0' && ch <= '9')
- {
- long t = Convert.ToInt64(ch);
- cnt = cnt * 10 + ch - '0';
- ch = Convert.ToChar(Console.Read());
- }
- return cnt * sign;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement