Grafos I

tags: upsolving ps2020 grafo

B

const int N = 105;
vector<int> adj[N];
vector<string> v;
char s[N];

void compara(int a, int b) {
  for(int i = 0; i < v[a].size() and i < v[b].size(); i++) {
    if(v[a][i] != v[b][i]) {
      adj[v[a][i]-'a'].pb(v[b][i]-'a');
      return;
    }
}

int main() {
  for(int i = 1; i < v.size(); i++) {
      compara(i-1, i);    
  }
}

E

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Ideia:
Guloso: Se um nó u é uma cidade de negócio, todas as árvores em sua ramificação também será uma cidade de negócio.

//type here


priority_queue<int> pq;

int dfs(int u, int l){
    if(vis[u])
        return 0;
    vis[u] = 1;
    
    int filhos = 0;
    for(int k : adj[u]){
      filhos += dfs(k, l+1);
     
    
    pq.push(l - filhos);
    
    return filhos + 1;
}