Remove Directed Edges Codeforces Solution | Codeforces Problem Solution 2022

Remove Directed Edges Codeforces Solution | Codeforces Problem Solution 2022

G. Remove Directed Edges

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a directed acyclic graph, consisting of 𝑛$n$ vertices and 𝑚$m$ edges. The vertices are numbered from 1$1$ to 𝑛$n$. There are no multiple edges and self-loops.

Let in𝑣${\mathit{i}\mathit{n}}_v$ be the number of incoming edges (indegree) and out𝑣${\mathit{o}\mathit{u}\mathit{t}}_v$ be the number of outgoing edges (outdegree) of vertex 𝑣$v$.

You are asked to remove some edges from the graph. Let the new degrees be in′𝑣${\mathit{i}{\mathit{n}}^{\prime }}_v$ and out′𝑣${\mathit{o}\mathit{u}{\mathit{t}}^{\prime }}_v$.

Solution Click Below:-  CLICK HERE

You are only allowed to remove the edges if the following conditions hold for every vertex 𝑣$v$:

• in′𝑣<in𝑣${\mathit{i}{\mathit{n}}^{\prime }}_v<{\mathit{i}\mathit{n}}_v$ or in′𝑣=in𝑣=0${\mathit{i}{\mathit{n}}^{\prime }}_v={\mathit{i}\mathit{n}}_v=0$;
• out′𝑣<out𝑣${\mathit{o}\mathit{u}{\mathit{t}}^{\prime }}_v<{\mathit{o}\mathit{u}\mathit{t}}_v$ or out′𝑣=out𝑣=0${\mathit{o}\mathit{u}{\mathit{t}}^{\prime }}_v={\mathit{o}\mathit{u}\mathit{t}}_v=0$.

Let's call a set of vertices 𝑆$S$ cute if for each pair of vertices 𝑣$v$ and 𝑢$u$ (𝑣≠𝑢$v\ne u$) such that 𝑣∈𝑆$v\in S$ and 𝑢∈𝑆$u\in S$, there exists a path either from 𝑣$v$ to 𝑢$u$ or from 𝑢$u$ to 𝑣$v$ over the non-removed edges.

Number Transformation Codeforces Solution

Remove Directed Edges Codeforces Solution

Desktop Rearrangement Codeforces Solution

Dictionary Codeforces Solution

Breaking the Wall Codeforces Solution

A-B-C Sort Codeforces Solution

Infinite Replacement Codeforces Solution 

What is the maximum possible size of a cute set 𝑆$S$ after you remove some edges from the graph and both indegrees and outdegrees of all vertices either decrease or remain equal to 0$0$?

Input

The first line contains two integers 𝑛$n$ and 𝑚$m$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$; 0≤𝑚≤2⋅105$0\le m\le 2\cdot {10}^5$) — the number of vertices and the number of edges of the graph.

Each of the next 𝑚$m$ lines contains two integers 𝑣$v$ and 𝑢$u$ (1≤𝑣,𝑢≤𝑛$1\le v,u\le n$; 𝑣≠𝑢$v\ne u$) — the description of an edge.

The given edges form a valid directed acyclic graph. There are no multiple edges.

Output

Print a single integer — the maximum possible size of a cute set 𝑆$S$ after you remove some edges from the graph and both indegrees and outdegrees of all vertices either decrease or remain equal to 0$0$.

Join Now for Solution:-