Aakash_DD's blog

By Aakash_DD, history, 4 months ago, In English,

I was solving some problems from contests but can't figure out how to solve this problem in the given time constraints.

My attempts: 1. I was making the brute force solution O(n^2). 2. I thought for Graphs and Connected components size but I m not able to do under given constraints.


4 months ago, # |
Rev. 9   Vote: I like it +13 Vote: I do not like it

The difficult part of this problem is the existence of a closed path, so firstly we use Decomposition of Strongly Connected Components (SCC) to group vertices. We consider vertexes as visited which constitutes SCC whose size is more than one and let dp [i] = size of SCC. After that, simply do dfs from each vertex and find maximum value of {(the number of vertices that have never been visited before reaching the vertex where you have visited) + (dp [i] (i is the vertex you have visited))}. There are N edges, so the complexity is O (T*(N+M))= O(T*N).

EDIT:Of course, while doing dfs, the vertices visited once will be treated as vertices that have been visited in the subsequent dfs, and dp[i] will be updated on the way back of dfs. Also, I omit the explanation for a[i] = i.