Fichas (2021-2022)

Resoluções Incorretas?

Caso encontres incorreções nas resoluções abaixo, por favor reporta-as para serem corrigidas.

Coletânea de Exercícios

A UC apresenta, para além das fichas indicadas abaixo, uma coletânea de exercícios mantida pelo professor Vasco Manquinho, acessível na página da cadeira no Fénix. Pode servir como bom complemento ao estudo!

As fichas de exercícios destinadas a cada aula prática costumam ser disponibilizadas na página da cadeira, acompanhadas pela respetiva (re)solução, pelo que não serão incluídas aqui.

Mais Resoluções

Se quiseres adicionar as tuas resoluções, podes sempre fazer um PR!

Prática 1: Projeto NULL

Implementação

#include <vector>
#include <iostream>

typedef std::vector<std::vector<int>> matrix;

int main()
{
  int people_in_network, relation_count;

  std::cin >> people_in_network;
  std::cin.ignore();
  std::cin >> relation_count;

  matrix m = {};

  // initialize vector
  for (int i = 0; i < people_in_network; ++i)
  {
    std::vector<int> vec = {};
    for (int j = 0; j < people_in_network; j++)
    {
      vec.push_back(0);
    }
    m.push_back(vec);
  }

  // populate relations
  for (int i = 0; i < relation_count; ++i)
  {
    int origin, target;
    std::cin >> origin >> target;

    m.at(origin - 1).at(target - 1)++;
  }

  // each row is the people with n friends
  std::vector<int> hist1(people_in_network, 0);
  // each row is how many people have n people as friends
  std::vector<int> hist2(people_in_network, 0);
  for (int i = 0; i < people_in_network; ++i)
  {
    int friend_count = 0;
    int inverse_friend_count = 0;
    for (int j = 0; j < people_in_network; ++j)
    {
      if (m.at(i).at(j) > 0)
      {
        ++friend_count;
      }
      if (m.at(j).at(i) > 0)
      {
        ++inverse_friend_count;
      }
    }
    hist1.at(friend_count)++;
    hist2.at(inverse_friend_count)++;
  }

  std::cout << "Histograma 1" << std::endl;
  for (size_t i = 0; i < hist1.size(); ++i)
  {
    std::cout << hist1.at(i) << std::endl;
  }

  std::cout << "Histograma 2" << std::endl;
  for (size_t i = 0; i < hist1.size(); ++i)
  {
    std::cout << hist2.at(i) << std::endl;
  }

  matrix common_friends;
  // initialize vector
  for (int i = 0; i < people_in_network; ++i)
  {
    std::vector<int> vec = {};
    for (int j = 0; j < people_in_network; j++)
    {
      vec.push_back(0);
    }
    common_friends.push_back(vec);
  }

  for (int i = 0; i < people_in_network; ++i)
  {
    for (int j = 0; j < people_in_network; ++j)
    {
      int common_count = 0;
      for (int k = 0; k < people_in_network; ++k)
      {
        if (m.at(i).at(k) > 0 && m.at(j).at(k) > 0)
        {
          ++common_count;
        }
      }
      common_friends.at(i).at(j) = common_count;
    }
  }

  std::cout << "Common Friends" << std::endl;

  for (int i = 0; i < people_in_network; ++i)
  {
    for (int j = 0; j < people_in_network; j++)
    {
      std::cout << common_friends.at(i).at(j);
    }
    std::cout << std::endl;
  }

  return 0;
}

#include <iostream>
#include <vector>

using namespace std;
typedef int Vertex;
typedef vector<vector<Vertex>> adjList;

class Graph {
  int noElements;
  adjList list;

  public:
    Graph(int noElements);
    void addEdge(Vertex u, Vertex v);
    int getNoElements();
    adjList getAdjList();
};

void parse(Graph &graph, Graph &transverse, int noRelationships);
void printHist(Graph graph, char num);
void printCommonMatrix(Graph graph);

Graph::Graph(int noElements) {
  this->noElements = noElements;
  list.resize(noElements);
}

void Graph::addEdge(Vertex u, Vertex v) {
  list[u].push_back(v);
}

int Graph::getNoElements() {
  return this->noElements;
}

adjList Graph::getAdjList() {
  return this->list;
}

int main() {
  int noPeople, noRelationships;
  scanf("%d,%d", &noPeople, &noRelationships);

  Graph graph = Graph(noPeople);
  Graph transverseGraph = Graph(noPeople);
  parse(graph, transverseGraph, noRelationships);

  printHist(graph, '1');
  printHist(transverseGraph, '2');
  printCommonMatrix(transverseGraph);

  return 0;
}

void parse(Graph &graph, Graph &transverse, int noRelationships) {
  for (int i = 0; i < noRelationships; i++) {
    Vertex person1, person2;
    scanf("%d %d", &person1, &person2);
    graph.addEdge(person1 - 1, person2 - 1);
    transverse.addEdge(person2 - 1, person1 - 1);
  }
}

void printHist(Graph graph, char num) {
  int noElements = graph.getNoElements();
  adjList list = graph.getAdjList();
  vector<int> degrees(noElements, 0);

  for (int i = 0; i < noElements; i++) {
    degrees[list[i].size()]++;
  }

  cout << "Histograma " << num << endl;
  for (int deg: degrees) {
    cout << deg << endl;
  }
}

void printCommonMatrix(Graph graph) {
  adjList list = graph.getAdjList();
  vector<vector<int>> commonMatrix(graph.getNoElements(), vector<int>(graph.getNoElements(), 0));
  for (uint i = 0; i < list.size(); i++) {
    for (uint j = 0; j < list[i].size(); j++) {
      for (uint k = j; k < list[i].size(); k++) {
        commonMatrix[j][k]++;
        if (j != k) commonMatrix[k][j]++; // not adding twice if j == k
      }
    }
  }
  for (vector<int> row: commonMatrix) {
    for (int amt: row) {
      cout << amt << " ";
    }
    cout << endl;
  }
}

#include <vector>
#include <iostream>
using namespace std;

typedef vector<vector<int>> graph;
typedef vector<vector<int>> matrix;
typedef vector<int> histogram;

void parse_input(graph &g, graph &gt) {
    uint n, m;
    char ignore;
    cin >> n >> ignore >> m;

    g = vector<vector<int>>(n, vector<int>());
    gt = vector<vector<int>>(n, vector<int>());

    for (uint i = 0; i < m; i++) {
        uint u, v;
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        gt[v - 1].push_back(u - 1);
    }
}

histogram make_histogram(const graph &g) {
    histogram h = vector<int>(g.size(), 0);

    for (uint i = 0; i < g.size(); i++) h[g[i].size()]++;

    return h;
}

void show_histogram(const histogram &h) {
    for (uint i = 0; i < h.size(); i++) cout << h[i] << '\n';
}

matrix make_matrix(const graph &g) {
    matrix m = vector<vector<int>>(g.size(), vector<int>(g.size(), 0));

    for (uint i = 0; i < m.size(); i++) {
        for (uint j = i; j < m[i].size(); j++) {
            if (i == j) {
                m[i][j] = g[i].size();
            } else {
                // Calculate histogram of friends known by the nodes,
                // If the frequency is 2 then both know it.
                histogram h = vector<int>(g.size(), 0);
                for (uint u = 0; u < g[i].size(); u++) h[g[i][u]]++;
                for (uint u = 0; u < g[j].size(); u++) h[g[j][u]]++;

                for (uint u = 0; u < h.size(); u++) {
                    if (h[u] == 2) {
                        // Increment matrix symetrically.
                        m[i][j]++;
                        m[j][i]++;
                    }
                }
            }
        }
    }

    return m;
}

void show_matrix(const matrix &m) {
    for (uint i = 0; i < m.size(); i++) {
        for (uint j = 0; j < m[i].size(); j++) {
            cout << m[i][j] << " ";
        }
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    graph g, gt;
    parse_input(g, gt);

    cout << "Histograma 1\n";
    show_histogram(make_histogram(g));
    cout << "Histograma 2\n";
    show_histogram(make_histogram(gt));
    cout << "Matrix\n";
    show_matrix(make_matrix(g));
}