VasilM

bfs biggest area

Apr 2nd, 2014
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.01 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int MAXN = 100;
  5. // списък на посетените върхове, списък на бащите и списък на съседите
  6. int used[MAXN+1] = {0}, parentsList[MAXN], neighboursList[MAXN][MAXN] = {0};
  7. // опашка, начален индекс, краен индекс
  8. int queue[MAXN], queBegin, queEnd;
  9. //
  10. int biggestAreaInd, areaInd = 1, biggestAreaSZ = 0;
  11.  
  12. // създаване на "празна" опашка
  13. void makeQueEmpty(){
  14.     queBegin=0;
  15.     queEnd=-1;
  16. }
  17.  
  18. // добавяне на елемент в опашвката
  19. void push(int x){
  20.     queue[ ++queEnd ]= x;
  21. }
  22.  
  23. // изваждане на елемент от опашката
  24. int pop(){
  25.     return queue[ queBegin++ ];
  26. }
  27.  
  28. // проверка за "празна" обашка
  29. // началото по-голямо ли е от края?
  30. bool isQueEmpty(){
  31.     return queBegin>queEnd;
  32. }
  33.  
  34. void BFS(int startingNode) {
  35.      
  36.   int  x,y;
  37.   int currentAreaSZ = 1;
  38.  
  39.   makeQueEmpty();
  40.   push( startingNode );
  41.   used[ startingNode ]= areaInd;
  42.   parentsList[ startingNode ]= 0;
  43.  
  44.   while(!isQueEmpty()) {                    
  45.     x=pop();    
  46.     for(int i=1; i <= neighboursList[x][0]; i++) {                            
  47.       y= neighboursList[x][i];      
  48.       if(!used[y]) {
  49.           push(y);
  50.           used[y]= areaInd;
  51.           currentAreaSZ++;
  52.           parentsList[ y ]= x;
  53.       }
  54.     }
  55.   }
  56.   if( biggestAreaSZ < currentAreaSZ ) {
  57.     biggestAreaSZ = currentAreaSZ;
  58.     biggestAreaInd = areaInd;
  59.   }
  60. }
  61.  
  62.  
  63. int main(){    
  64.     int N,M,x,y; // N - бр. върхове, M - бр. ребра
  65.     cin >> N >> M;
  66.        
  67.     while( M-- ){
  68.         cin >> x >> y;
  69.         neighboursList[ x ][ ++neighboursList[x][0] ] = y;
  70.         neighboursList[ y ][ ++neighboursList[y][0] ] = x;
  71.     }
  72.  
  73.     for(int i=1;i<=N;i++) {
  74.         if(used[i]==0) {
  75.             BFS(i);
  76.             areaInd++;
  77.         }
  78.     }
  79.  
  80.     cout << biggestAreaSZ << endl;
  81.    
  82.     for(int i=1; i<=N; i++ ) {
  83.         if ( used[i] == biggestAreaInd ) {
  84.             cout << i <<" ";
  85.         }
  86.     }
  87.    
  88.     cout << endl;
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment