Solução de Matheus, comentário por João Guilherme
Para ver o problema original, clique aqui.
A solução é uma aplicação direta da aula sobre flood fill, para vê-la clique aqui. Então o que devemos fazer é ligar dois impérios se um deles atacar o outro. Depois nós passamos por cada império e vemos se ele já foi colorido, se não usamos uma BFS(ou DFS) para pintar todos os seus vizinhos, assim usando um contador para contar o número de componentes conexos.
Segue o 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 <cstdio> | |
| #include <vector> | |
| #include <queue> | |
| using namespace std; | |
| int main() | |
| { | |
| int m, n, i, j, a, b, cont = 0, z; | |
| scanf("%d%d", &n, &m); | |
| vector<int> v [n+1]; | |
| int imperio[n+1]; | |
| queue<int> f; | |
| for(i=0;i<m;i++) | |
| { | |
| scanf("%d %d", &a, &b); | |
| v[a].push_back(b); | |
| v[b].push_back(a); | |
| } | |
| for(i=1;i<=n;i++) | |
| imperio[i] = -1; | |
| for(i=1;i<=n;i++) | |
| { | |
| if(imperio[i] == -1) | |
| { | |
| cont++; | |
| imperio[i] = cont; | |
| f.push(i); | |
| while(!f.empty()) | |
| { | |
| z = f.front(); | |
| f.pop(); | |
| for(j=0;j<v[z].size();j++) | |
| { | |
| if(imperio[v[z][j]] == -1){ | |
| imperio[v[z][j]] = imperio[z]; | |
| f.push(v[z][j]); | |
| } | |
| } | |
| } | |
| } | |
| } | |
| printf("%d", cont); | |
| } |