Remove Directed Edges solution codeforces – You are given a directed acyclic graph, consisting of 𝑛n vertices and 𝑚m edges. The vertices are numbered from 11 to 𝑛n. There are no multiple edges and self-loops.
[Solution] Remove Directed Edges solution codeforces
Let in𝑣inv be the number of incoming edges (indegree) and out𝑣outv 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′𝑣in′v and out′𝑣out′v.
You are only allowed to remove the edges if the following conditions hold for every vertex 𝑣v:
- in′𝑣<in𝑣in′v<inv or in′𝑣=in𝑣=0in′v=inv=0;
- out′𝑣<out𝑣out′v<outv or out′𝑣=out𝑣=0out′v=outv=0.
Let’s call a set of vertices 𝑆S cute if for each pair of vertices 𝑣v and 𝑢u (𝑣≠𝑢v≠u) such that 𝑣∈𝑆v∈S and 𝑢∈𝑆u∈S, there exists a path either from 𝑣v to 𝑢u or from 𝑢u to 𝑣v over the non-removed edges.
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 00?
The first line contains two integers 𝑛n and 𝑚m (1≤𝑛≤2⋅1051≤n≤2⋅105; 0≤𝑚≤2⋅1050≤m≤2⋅105) — 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≤v,u≤n; 𝑣≠𝑢v≠u) — the description of an edge.
The given edges form a valid directed acyclic graph. There are no multiple edges.
[Solution] Remove Directed Edges solution codeforces
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 00.
3 3 1 2 2 3 1 3
2
[Solution] Remove Directed Edges solution codeforces
5 0
1
7 8 7 1 1 3 6 2 2 3 7 2 2 4 7 3 6 3
3
Remove Directed Edges solution codeforces
In the first example, you can remove edges (1,2)(1,2) and (2,3)(2,3). in=[0,1,2]in=[0,1,2], out=[2,1,0]out=[2,1,0]. in′=[0,0,1]in′=[0,0,1], out′=[1,0,0]out′=[1,0,0]. You can see that for all 𝑣v the conditions hold. The maximum cute set 𝑆S is formed by vertices 11 and 33. They are still connected directly by an edge, so there is a path between them.
In the second example, there are no edges. Since all in𝑣inv and out𝑣outv are equal to 00, leaving a graph with zero edges is allowed. There are 55 cute sets, each contains a single vertex. Thus, the maximum size is 11.
In the third example, you can remove edges (7,1)(7,1), (2,4)(2,4), (1,3)(1,3) and (6,2)(6,2). The maximum cute set will be 𝑆={7,3,2}S={7,3,2}. You can remove edge (7,3)(7,3) as well, and the answer won’t change.
Here is the picture of the graph from the third example:
