Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- vector<int> G[1000008];
- int odw[1000008];
- int odl[1000008];
- int wybieg[1000008];
- queue<int> Q;
- int krawedzie, wezly, a, b, w, v, wynik=INT_MAX;
- void czytaj();
- void wypisz_graf();
- void wypisz_ojca();
- void wypisz_odl();
- void BFS(int s);
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(NULL);
- czytaj();
- for(int i=1; i<=wezly; i++)
- {
- if(wybieg[i]==0)BFS(i);
- }
- wypisz_odl();
- cout<<wynik;
- return 0;
- }
- void czytaj()
- {
- cin>>wezly>>krawedzie;
- for(int i=1; i<=wezly; i++)
- {
- cin>>wybieg[i];
- }
- for(int i=1; i<=krawedzie; i++)
- {
- cin>>a>>b;
- G[a].push_back(b);
- G[b].push_back(a);
- }
- }
- void BFS(int s)
- {
- odw[s]=1;
- odl[s]=0;
- Q.push(s);
- while(!Q.empty())
- {
- w=Q.front();
- Q.pop();
- for(int i=0; i<G[w].size(); i++)
- {
- int v=G[w][i];
- if(odw[v]==0)
- {
- odw[v]=1;
- if(odl[v]==0 || odl[w]+1 < odl[v])odl[v]=odl[w]+1;
- Q.push(v);
- }
- }
- }
- }
- void wypisz_odl()
- {
- for(int i=1; i<=wezly; i++)
- {
- if(wybieg[i]==1 && odl[i]<wynik)
- {
- wynik=odl[i];
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement