Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- const int MAXN = 100;
- // списък на посетените върхове, списък на бащите и списък на съседите
- int used[MAXN+1] = {0}, parentsList[MAXN], neighboursList[MAXN][MAXN] = {0};
- // опашка, начален индекс, краен индекс
- int queue[MAXN], queBegin, queEnd;
- //
- int biggestAreaInd, areaInd = 1, biggestAreaSZ = 0;
- // създаване на "празна" опашка
- void makeQueEmpty(){
- queBegin=0;
- queEnd=-1;
- }
- // добавяне на елемент в опашвката
- void push(int x){
- queue[ ++queEnd ]= x;
- }
- // изваждане на елемент от опашката
- int pop(){
- return queue[ queBegin++ ];
- }
- // проверка за "празна" обашка
- // началото по-голямо ли е от края?
- bool isQueEmpty(){
- return queBegin>queEnd;
- }
- void BFS(int startingNode) {
- int x,y;
- int currentAreaSZ = 1;
- makeQueEmpty();
- push( startingNode );
- used[ startingNode ]= areaInd;
- parentsList[ startingNode ]= 0;
- while(!isQueEmpty()) {
- x=pop();
- for(int i=1; i <= neighboursList[x][0]; i++) {
- y= neighboursList[x][i];
- if(!used[y]) {
- push(y);
- used[y]= areaInd;
- currentAreaSZ++;
- parentsList[ y ]= x;
- }
- }
- }
- if( biggestAreaSZ < currentAreaSZ ) {
- biggestAreaSZ = currentAreaSZ;
- biggestAreaInd = areaInd;
- }
- }
- int main(){
- int N,M,x,y; // N - бр. върхове, M - бр. ребра
- cin >> N >> M;
- while( M-- ){
- cin >> x >> y;
- neighboursList[ x ][ ++neighboursList[x][0] ] = y;
- neighboursList[ y ][ ++neighboursList[y][0] ] = x;
- }
- for(int i=1;i<=N;i++) {
- if(used[i]==0) {
- BFS(i);
- areaInd++;
- }
- }
- cout << biggestAreaSZ << endl;
- for(int i=1; i<=N; i++ ) {
- if ( used[i] == biggestAreaInd ) {
- cout << i <<" ";
- }
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment