Help in graph problem 1 :)

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 ( 1n ≤ 105 ) and m ( n - 1m ≤ 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 ( 1kn ) – 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.

Input example #1

6 6
1 2
2 6
1 5
5 6
3 5
4 5
2
1 2

Output example #1

2
3

Explaination :

Screenshot_2020-06-24 Breadth First Search - Introduction - E-Olymp

Q : https://www.e-olymp.com/en/contests/16462/problems/170300
solution - > My_Solution

I m getting TLE and WA in some of cases … help @galencolin @carre @hetp111 @waqar_ahmad224 @nuttela @nishant403

my solution

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 }

why does this problem look like we just got to do bfs traversal on the nodes and the nodes with lowest depth will be our answer?

If there are more than 1 node in the lowest depth, then print the minimum-value node.

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?

1 Like

Increase time only if “last” node is changing.

1 Like

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.

there could be multiple solutions also right ? like for above example solution also could have been
2
4

Out of 3 and 4, you choose the minimum node number to print. So the answer is unique and is

2
3
1 Like

Runtime error and WA’s

53% pass only :slight_smile:

multisource bfs should work I think.

Isn’t that what I’ve done here? Apparently doesn’t pass. :confused:

[EDIT]: Had done a small mistake, edited it in the code above.

1 Like

100% AC code, bfs implementatin inspired from anee004 code

#include<bits/stdc++.h>
using namespace std;
#define INF ((int)(1e9+7))
int main(){
	int n,m;
	cin >> n >> m;
	vector<int> v[n];
	for(int i=0;i<m;i++){
		int x,y;
		cin >> x >> y;
		x--,y--;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	int k;
	cin >> k;
	queue<int> q;
	vector<int> visited(n,false);
	for(int i=0;i<k;i++){
		int x;
		cin >> x;
		x--;
		q.push(x);
		visited[x] = true;
	}	
	//given k>1
	int time = 0;
	int last;
	while(!q.empty()){
		int size = q.size();
		vector<int> in_this_level;
		while(size--){
			int s = q.front();
			q.pop();
			for(auto x : v[s]){
				if(!visited[x]){
					visited[x] = true;
					in_this_level.push_back(x);
					last = x;
					q.push(x);
				}
			}
		}
		if(in_this_level.size())time++;
		for(auto y : in_this_level)
			last = min(last,y);
	}
	cout << time << endl << last+1 << endl;
}
2 Likes

Multisource BFS (using queue of pair ) solved , thanks evryone :slight_smile:

solution

i also solved it https://www.e-olymp.com/en/submissions/7147662.

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

3 Likes

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 :slight_smile:

2 Likes