TOPIC

não sei pq 5%

Felipe298 asked 4 years ago

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

vector <int> mark;
vector < vector <int> > grafo;
int cont;

void DFS(int v){
  cont++;
  mark[v] = 1;
  for(int i = 0; i < grafo[v].size(); i++){
    int adj = grafo[v][i];
    if(!mark[adj]){
      DFS(adj);
    }
  }
}
bool comp(int a, int b){
  return a > b;
}

int main(){

  ios_base::sync_with_stdio(0);
  int x;
  cin >> x;
  vector <int> aux;
  grafo.resize(x, aux);
  string r;
  for(int i = 0; i < x; i++){
    cin >> r;
    for(int j = 0; j < r.size(); j++){
      if(r[j] == 'S'){
        grafo[i].push_back(j);
      }
    }
  }
  mark.resize(x, 0);
  vector <int> vetor;
  for(int i = 0; i < x; i++){
    cont = 0;
    if(!mark[i]){
      DFS(i);
    }
    if(cont > 0)
      vetor.push_back(cont);
  }
  if(vetor.size() <= 1)
    cout << "-1\n";
  else{
    cout << vetor.size() << endl;
    sort(vetor.begin(), vetor.end(), comp);
    for(int i = 0; i < vetor.size(); i++){
      if(i)
        cout << ' ';
      cout << vetor[i];
    }
    cout << endl;    
  }  

  return 0;
  }

Remember not post solutions. Your post may be reviewed by our moderators.

  • feodorv replied 4 years ago

    How do you use 'N' information? There can be discrepancy with the 'S' information...