Hi. I am trying to solve [this](https://dunjudge.me/analysis/problems/1433/) problem.↵
↵
For convenience, I have summarized the problem statement below (based on my understanding):↵
↵
_Given a directed graph with $N$ vertices and $E$ edges (with cycles and not necessarily connected), find the minimum number of edges that we need to retain such that connectivity between vertices is retained as given in the original graph._↵
↵
Input size: $ 1 \le N, E \le 2e5 $ <br/>↵
Time limit: $1s$↵
↵
For example, for the following graph:↵
↵
<img src="https://image.ibb.co/jox8C6/graph.png" alt="graph" border="0">↵
↵
We should retain the edges:↵
↵
↵
~~~~~↵
0 -> 1↵
1 -> 2↵
1 -> 3↵
~~~~~↵
↵
So we must use a minimum of 3 edges.↵
↵
Note that:<br/>↵
`0 -> 2` is redundant as we can use the path `0 -> 1 -> 2` to get from `0` to `2`.<br/>↵
`0 -> 3` is redundant as we can use the path `0 -> 1 -> 3` to get from `0` to `3`. (Thanks [user:filippos,2017-12-14] for catching this mistake!)<br/>↵
↵
This problem seems to be asking for the transitive reduction of a graph which can only be found in at least $O(n^2)$ based on what I found on Google and this clearly wouldn't pass the time limit. Furthermore, the list of AC solutions suggests that there is a linear time solution to this problem.↵
↵
Could someone please advise me on how to solve this problem?↵
↵
**UPD** Managed to solve this problem (thank you [user:yosei-san,2017-12-16] for your incredible patience and explanation!).↵
↵
I indeed had a wrong understanding of this problem and overly constrained it.↵
↵
For readers who are looking for the solution to this problem, I have posted my solution below:↵
↵
<spoiler summary="My approach">↵
↵
Initially, we build a graph where the nodes represent towns and edges represent the direction of required trips between two towns.↵
↵
Now we view this graph as an **undirected** graph. Clearly, the graph has at least 1 connected component.↵
↵
Then, we separate the original graph into its connected components (i.e no edges exist between components). Some possible ways to do this are DFS and DSU. ↵
↵
Now that we have **disjoint** components of the graph, we "restore" the direction of the graph's edges (i.e. view it as a directed graph again).↵
↵
For each component, clearly, it either has cycle(s) or it is a DAG.↵
↵
If a component has a cycle among some of its nodes (and assuming it has K nodes), we can easily include all nodes into the cycle by doing 1 -> 2 -> ... -> K -> 1. So we need to add K edges, for each of these components, to the answer.↵
↵
If a component is a DAG (and assuming it has K nodes), the last node in the topological sort order of the component doesn't need to navigate anywhere else. So we only add K — 1 edges, for each of these components, to the answer.↵
↵
Hence the final answer is #Towns — #DAGs.↵
↵
</spoiler>↵
↵
<spoiler summary="My accepted code">↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int maxn = 2e5 + 5;↵
int n, m, a, b, ans, par[maxn];↵
vector<int> to[maxn];↵
bool has[maxn], vis[maxn];↵
unordered_set<int> path;↵
↵
int find(int u) {↵
return par[u] == u ? u : par[u] = find(par[u]);↵
}↵
↵
void dfs(int u) {↵
vis[u] = 1;↵
path.insert(u);↵
for(int i = 0; i < (int) to[u].size(); i++) {↵
int v = to[u][i];↵
if(find(u) != find(v)) {↵
continue;↵
}↵
if(vis[v] && path.find(v) != path.end()) {↵
has[find(v)] = 1;↵
}↵
if(!vis[v]) {↵
dfs(v);↵
}↵
}↵
path.erase(u);↵
}↵
↵
void addEdge(int u, int v) {↵
to[u].push_back(v);↵
par[find(u)] = find(v);↵
}↵
↵
int main() {↵
scanf("%d %d", &n, &m);↵
↵
ans = n;↵
↵
for(int i = 0; i < n; i++) {↵
par[i] = i;↵
}↵
for(int i = 0; i < m; i++) {↵
scanf("%d %d", &a, &b);↵
addEdge(a, b);↵
}↵
for(int i = 0; i < n; i++) {↵
int r = find(i);↵
if(has[r]) {↵
vis[i] = 1;↵
}↵
if(!vis[i]) {↵
dfs(i);↵
}↵
}↵
for(int i = 0; i < n; i++) {↵
int r = find(i);↵
if(vis[i] && !has[r]) {↵
has[r] = 1;↵
ans--;↵
}↵
}↵
printf("%d\n", ans);↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
For convenience, I have summarized the problem statement below (based on my understanding):↵
↵
_Given a directed graph with $N$ vertices and $E$ edges (with cycles and not necessarily connected), find the minimum number of edges that we need to retain such that connectivity between vertices is retained as given in the original graph._↵
↵
Input size: $ 1 \le N, E \le 2e5 $ <br/>↵
Time limit: $1s$↵
↵
For example, for the following graph:↵
↵
<img src="https://image.ibb.co/jox8C6/graph.png" alt="graph" border="0">↵
↵
We should retain the edges:↵
↵
↵
~~~~~↵
0 -> 1↵
1 -> 2↵
1 -> 3↵
~~~~~↵
↵
So we must use a minimum of 3 edges.↵
↵
Note that:<br/>↵
`0 -> 2` is redundant as we can use the path `0 -> 1 -> 2` to get from `0` to `2`.<br/>↵
`0 -> 3` is redundant as we can use the path `0 -> 1 -> 3` to get from `0` to `3`. (Thanks [user:filippos,2017-12-14] for catching this mistake!)<br/>↵
↵
This problem seems to be asking for the transitive reduction of a graph which can only be found in at least $O(n^2)$ based on what I found on Google and this clearly wouldn't pass the time limit. Furthermore, the list of AC solutions suggests that there is a linear time solution to this problem.↵
↵
Could someone please advise me on how to solve this problem?↵
↵
**UPD** Managed to solve this problem (thank you [user:yosei-san,2017-12-16] for your incredible patience and explanation!).↵
↵
I indeed had a wrong understanding of this problem and overly constrained it.↵
↵
For readers who are looking for the solution to this problem, I have posted my solution below:↵
↵
<spoiler summary="My approach">↵
↵
Initially, we build a graph where the nodes represent towns and edges represent the direction of required trips between two towns.↵
↵
Now we view this graph as an **undirected** graph. Clearly, the graph has at least 1 connected component.↵
↵
Then, we separate the original graph into its connected components (i.e no edges exist between components). Some possible ways to do this are DFS and DSU. ↵
↵
Now that we have **disjoint** components of the graph, we "restore" the direction of the graph's edges (i.e. view it as a directed graph again).↵
↵
For each component, clearly, it either has cycle(s) or it is a DAG.↵
↵
If a component has a cycle among some of its nodes (and assuming it has K nodes), we can easily include all nodes into the cycle by doing 1 -> 2 -> ... -> K -> 1. So we need to add K edges, for each of these components, to the answer.↵
↵
If a component is a DAG (and assuming it has K nodes), the last node in the topological sort order of the component doesn't need to navigate anywhere else. So we only add K — 1 edges, for each of these components, to the answer.↵
↵
Hence the final answer is #Towns — #DAGs.↵
↵
</spoiler>↵
↵
<spoiler summary="My accepted code">↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int maxn = 2e5 + 5;↵
int n, m, a, b, ans, par[maxn];↵
vector<int> to[maxn];↵
bool has[maxn], vis[maxn];↵
unordered_set<int> path;↵
↵
int find(int u) {↵
return par[u] == u ? u : par[u] = find(par[u]);↵
}↵
↵
void dfs(int u) {↵
vis[u] = 1;↵
path.insert(u);↵
for(int i = 0; i < (int) to[u].size(); i++) {↵
int v = to[u][i];↵
if(find(u) != find(v)) {↵
continue;↵
}↵
if(vis[v] && path.find(v) != path.end()) {↵
has[find(v)] = 1;↵
}↵
if(!vis[v]) {↵
dfs(v);↵
}↵
}↵
path.erase(u);↵
}↵
↵
void addEdge(int u, int v) {↵
to[u].push_back(v);↵
par[find(u)] = find(v);↵
}↵
↵
int main() {↵
scanf("%d %d", &n, &m);↵
↵
ans = n;↵
↵
for(int i = 0; i < n; i++) {↵
par[i] = i;↵
}↵
for(int i = 0; i < m; i++) {↵
scanf("%d %d", &a, &b);↵
addEdge(a, b);↵
}↵
for(int i = 0; i < n; i++) {↵
int r = find(i);↵
if(has[r]) {↵
vis[i] = 1;↵
}↵
if(!vis[i]) {↵
dfs(i);↵
}↵
}↵
for(int i = 0; i < n; i++) {↵
int r = find(i);↵
if(vis[i] && !has[r]) {↵
has[r] = 1;↵
ans--;↵
}↵
}↵
printf("%d\n", ans);↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
