Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* Feladat: Mester / Gráfok, szélességi bejárás / Adott ponton átmenő legrövidebb kör */
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <climits>
- #define MAXN 10000
- #define MAXM 200000
- using namespace std;
- int N, M, P;
- vector<int> ponts[MAXN+1];
- int szint[MAXN+1];
- int ancestor[MAXN+1];
- int
- main()
- {
- ios_base::sync_with_stdio(false);
- cin >> N >> M >> P;
- for(int i = 0; i < M; i++){
- int a, b;
- cin >> a >> b;
- ponts[a].push_back(b);
- ponts[b].push_back(a);
- }
- queue<int> sor;
- sor.push(P);
- sor.push(0);
- int hossz = 2;
- int minn = INT_MAX;
- int a, b;
- szint[P] = 1;
- do{
- int most = sor.front();
- sor.pop();
- if(!most){
- hossz++;
- if(minn != INT_MAX){
- cout << (minn-1) << endl;
- stack<int> ss;
- ss.push(a);
- do{
- a = ancestor[a];
- ss.push(a);
- }while(a != P);
- do{
- int kk = ss.top();
- ss.pop();
- cout << kk << " ";
- }while(!ss.empty());
- do{
- cout << b << " ";
- b = ancestor[b];
- }while(b != P);
- cout << endl;
- return 0;
- }
- sor.push(0);
- }else{
- for(const auto c : ponts[most]){
- if(!szint[c]){
- ancestor[c] = most;
- szint[c] = hossz;
- sor.push(c);
- }else if(c != ancestor[most]){
- int tm = szint[c] + szint[most];
- if(tm < minn){
- minn = tm;
- a = c;
- b = most;
- }
- }
- }
- }
- }while(!sor.empty());
- cout << "-1" << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement