There is a common web in front of you. However, as an experienced contester, you noticed that it is a connected graph with n vertices and m edges. If you fire some vertex, it will lights up, after a second all adjacent vertices light up, then all adjacent ones with already burning will light up, etc.
You know which vertices will be fired in the web (all at the same time). Find how many seconds will pass until the last vertex lights up and find this vertex.
Input
First line contains integers n ( 1 ≤ n ≤ 105 ) and m ( n - 1 ≤ m ≤ 105 ). Each of the next m lines contains two numbers – the vertex numbers connected with an edge. The vertices are numbered starting from 1 .
Next line contains number k ( 1 ≤ k ≤ n ) – the number of points to fire. Next line contains the numbers of k vertices to be fired.
Output
In the first line print the time when the last vertex will light up. In the second line print the number of this vertex. If there are several of them, print the one with minimum number.
This is my approach to the problem. (Not entirely sure about its correctness, I wrote it just now. If you spot a bug please let me know. It passes the sample test case though).
Code
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int INF = 987654321;
4
5 int main()
6 {
7 int n, m;
8 cin >> n >> m;
9 vector<int> adj[n];
10 for(int i = 0, u, v; i < m; i++)
11 {
12 cin >> u >> v; u--; v--;
13 adj[u].push_back(v);
14 adj[v].push_back(u);
15 }
16 int k, time = -1, last = 0;
17 queue<int> q;
18 vector<bool> vis(n, false);
19 cin >> k;
20 for(int i = 0, f; i < k; i++)
21 {
22 cin >> f; f--;
23 q.push(f);
24 vis[f] = 1;
25 }
26 while(not q.empty())
27 {
28 int sz = q.size();
29 int f = INF;
30 while(sz--)
31 {
32 int cur = q.front(); q.pop();
33 for(int i : adj[cur]) if(not vis[i])
34 {
35 q.push(i);
36 vis[i] = 1;
37 fin = min(fin, i + 1);
38 }
39 if(fin != INF)
40 last = fin;
41 }
42 time++;
43 }
44 cout << time << "\n" << last << "\n";
45 }
You have do to a bfs for each firing node. In that case the complexity is O(k(V + E))? And as k can go upto 10^5, the overall complexity should be O(n^2), which would not pass if there are strong test cases right?
The last node will change every time the inner while loop finishes execution. If it’s not, then the queue will be empty the the outer while loop with break. time will be incremented one final time when last is not changing (which is an extra increment), so I have initialized time as -1.
I see you solved it, good! I checked your initial approach and I think is important that you try to understand why that solution gave you both WA and TLE
Yeah thanks buddy … actually i applied wrong approach (still it passed 60%) and thus it is N2 it gave me tle … after some struggle i applied new approach and boom it passes