{"id":596,"date":"2016-11-21T00:00:22","date_gmt":"2016-11-21T02:00:22","guid":{"rendered":"http:\/\/www.galirows.com.br\/meublog\/programacao\/?p=596"},"modified":"2021-06-18T15:22:41","modified_gmt":"2021-06-18T18:22:41","slug":"cidades-interligadas","status":"publish","type":"post","link":"http:\/\/www.galirows.com.br\/meublog\/programacao\/cidades-interligadas\/","title":{"rendered":"Exerc\u00edcio cidades interligadas – complexo com matriz [incompleto]"},"content":{"rendered":"\n

Exerc\u00edcio bem interessante relacionado com a log\u00edstica de transporte. Ele permite uma associa\u00e7\u00e3o gr\u00e1fica o que tamb\u00e9m \u00e9 interessante, al\u00e9m de diversas partes, podendo ser selecionadas quais partes s\u00e3o de interesse (elas possuem n\u00edvel de dificuldade variados).<\/p>\n\n\n\n\n\n\n\n

Considere n<\/i> cidades numeradas de 0 a n<\/i>-1 que est\u00e3o interligadas por uma s\u00e9rie de estradas de m\u00e3o \u00fanica. As liga\u00e7\u00f5es entre as cidades s\u00e3o representadas pelos elementos de uma matriz quadrada  Lnxn<\/sub><\/i>, cujos elementos lij<\/sub><\/i> assumem o valor 1 ou 0, conforme exista ou n\u00e3o estrada direta que saia da cidade i<\/i> e chegue \u00e0 cidade j<\/i>. Assim, os elementos da linha i<\/i> indicam as estradas que saem da cidade i<\/i>, e os elementos da coluna j<\/i> indicam as estradas que chegam \u00e0 cidade j<\/i>.<\/p>\n\n\n\n

Por conven\u00e7\u00e3o lii<\/sub><\/i> = 1. A figura mostra um exemplo para n<\/i> = 4.<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
  • A) Dado k<\/i>, determinar quantas estradas saem e quantas chegam \u00e0 cidade k<\/i>.<\/li>
  • B) Dado k<\/i>, verificar se todas as liga\u00e7\u00f5es diretas entre a cidade k<\/i> e outras s\u00e3o de m\u00e3o dupla.<\/li>
  • C) Relacionar as cidades que possuem sa\u00eddas diretas para a cidade k<\/i>.<\/li>
  • D) A qual das cidades chega o maior n\u00famero de estradas?<\/li><\/ul>\n\n\n\n
    #include <stdio.h>\n#define TAM 4\n\nint main() {\n    int i, j, k, contIn=0, contOut=0, cont=0, contMaior=-1, cidadeMaior=-1;\n    int L[TAM][TAM] = {1, 1, 1, 0,\n                       0, 1, 1, 0,\n                       1, 0, 1, 1,\n                       0, 0, 1, 1};\n\n    \/\/A) Dado k, determinar quantas estradas saem e quantas chegam \u00e0 cidade k.\n    printf(\"Informe o numero da cidade (entre 0 e %d): \", TAM - 1);\n    scanf(\"%d\", &k);\n    for (i = 0; i < TAM; i++) {\n        if (k != i) { \/\/desconsidera a pr\u00f3pria cidade\n            if (L[i][k] == 1) { contIn++; }\n            if (L[k][i] == 1) { contOut++; }\n        }\n    }\n    printf(\"%d estradas saem e %d estradas chegam\\n\", contOut, contIn);\n\n    \/\/B) Dado k, verificar se todas as liga\u00e7\u00f5es diretas entre a cidade k e outras s\u00e3o de m\u00e3o dupla.\n    for (i = 0; i < TAM; i++) {\n        if (k != i) { \/\/desconsidera a pr\u00f3pria cidade\n            if ((L[i][k] == 1) && (L[k][i] == 1)) {\n                cont++;\n            }\n        }\n    }\n    printf(\"%d estradas de mao dupla\\n\", cont);\n\n    \/\/C) Relacionar as cidades que possuem sa\u00eddas diretas para a cidade k.\n    printf(\"Saidas diretas para a cidade: \");\n    for (i = 0; i < TAM; i++) {\n        if (k != i) { \/\/desconsidera a pr\u00f3pria cidade\n            if (L[i][k] == 1) {\n                printf(\"%i \", i);\n            }\n        }\n    }\n    printf(\"\\n\");\n\n    \/\/D) A qual das cidades chega o maior n\u00famero de estradas?\n    for (i = 0; i < TAM; i++) {\n        cont = 0;\n        for (j = 0; j < TAM; j++) {\n            if (L[j][i] == 1) {\n                    cont++;\n            }\n        }\n        if (cont > contMaior) {\n            contMaior = cont;\n            cidadeMaior = i;\n        }\n    }\n    printf(\"Cidade com maior numero de estradas: %d (com %d estradas)\\n\", cidadeMaior, contMaior-1);\n\n    return 0;\n}\n<\/code><\/pre>\n\n\n\n
    ================== Parte faltante do exerc\u00edcio ==============<\/p>\n\n\n\n
    E) Relacionar, se existirem cidades isoladas (cidades que n\u00e3o t\u00eam liga\u00e7\u00e3o com nenhuma outra) e cidades das quais n\u00e3o h\u00e1 sa\u00edda.<\/p>\n\n\n\n
    F) Dada uma sequ\u00eancia de m<\/i> inteiros cujos valores est\u00e3o entre 0 e n<\/i>-1, verificar se \u00e9 poss\u00edvel realizar o roteiro correspondente. No exemplo dado, o roteiro representado pela sequ\u00eancia (m<\/i>=5) 2 3 2 1 0 \u00e9 imposs\u00edvel.<\/p>\n\n\n\n
    G) Dados k<\/i> e p<\/i>, determinar se \u00e9 poss\u00edvel ir da cidade k <\/i>para a cidade p<\/i> pelas estradas existentes.<\/p>\n\n\n\n
    G.1) Qual o menor caminho entre as duas cidades?<\/p>\n\n\n\n
    H) Dado k<\/i>, determinar se \u00e9 poss\u00edvel, partindo de k<\/i>, passar por todas as outras cidades apenas uma vez e retornar a k<\/i>.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Exerc\u00edcio bem interessante relacionado com a log\u00edstica de transporte. Ele permite uma associa\u00e7\u00e3o gr\u00e1fica o que tamb\u00e9m \u00e9 interessante, al\u00e9m de diversas partes, podendo ser selecionadas quais partes s\u00e3o de interesse (elas possuem n\u00edvel de dificuldade variados).<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[3],"tags":[13],"class_list":["post-596","post","type-post","status-publish","format-standard","hentry","category-c","tag-matriz"],"aioseo_notices":[],"amp_enabled":true,"_links":{"self":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts\/596","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/comments?post=596"}],"version-history":[{"count":9,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts\/596\/revisions"}],"predecessor-version":[{"id":1067,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts\/596\/revisions\/1067"}],"wp:attachment":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/media?parent=596"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/categories?post=596"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/tags?post=596"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}