Esse é um problema que pode ser resolvido com grafos.
Vamos considerar cada ligação entre dois animais como uma aresta, e cada animal um vértice. A partir disso é possível ver que cada componente conexo é uma espécie, então reduzimos o problema a contar o número de componentes conexos nesse grafo.
Isso pode ser feito com uma simples DFS que marca todos os elementos que fazem parte de um componete conexo, e conforme passamos pelos vértices, marcamos todos que estão no mesmo componente que ele. Caso um vértice não tenha sido marcado, adicionamos 1 a contagem de componentes.
Código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bit/stdc++.h> | |
| using namespace std; | |
| const int maxn = 100010; | |
| vector<int> v[maxn]; | |
| int vis[maxn]; | |
| void dfs(int x) | |
| { | |
| vis[x] = 1; | |
| for (int u : v[x]) if (!vis[u]) dfs(u); | |
| } | |
| int main() | |
| { | |
| int n, m; | |
| cin >> n >> m; | |
| for (int i = 0; i < m; i++) { | |
| int a, b; | |
| cin >> a >> b; | |
| v[a].push_back(b); | |
| v[b].push_back(a); | |
| } | |
| int ans = 0; | |
| for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i), ans++; | |
| cout << ans << "\n"; | |
| } |