Por Samyra Almeida.
Para esse problema é necessário conhecimento sobre DFS.
Note que a mesa é dividida em dois lados, o lado da esquerda e o da direita, ou seja, se eu estou na direita meus amigos estarão na esquerda e vice-versa.
Com isso vamos tentar dividir nosso grafo da seguinte maneira: se eu estou na direita me pinto de 1 e pinto meus amigos de 2 (esquerda), e os amigos dos meus amigos, que não são meus amigos, serão pintados de 1 e assim sucessivamente.
Iremos fazer uma DFS que retorna true se conseguir dividir os amigos e false caso contrário.
Assim nosso algoritmo fica: ao chamar um nó DFS que ainda não foi visitado, coloco ele no lado direito da mesa e percorro sua lista de amigos se o amigos não foi visitado coloco ele do lado esquerdo(2) da mesa e chamo a dfs nele e então percorro sua lista de amigos, só que dessa vez coloco seus amigos do lado direito da mesa e assim sucessivamente, se ele já foi visitado checo estamos do mesmo lado da mesa se sim, retorno false, se não continuo percorrendo a minha lista de amigos, se em nenhum momento da DFS encontrarmos dois amigos do mesmo lado da mesa, retorno true.
Segue código solução para maior 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 <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 110; | |
| // declaro as variáveis que vou utilizar | |
| int n, m, comp[maxn], mesa[maxn]; | |
| vector<int> friends[maxn]; | |
| bool dfs(int x) | |
| { | |
| for(int i = 0 ; i < friends[x].size() ; ++i) // percorro a lista de amigos | |
| { | |
| int w = friends[x][i]; | |
| if(!comp[w]) // se ele não foi visitado | |
| { | |
| comp[w] = 1; // visito | |
| // coloco meu amigo em seu respectivo lado da mesa | |
| if(mesa[x] == 1) mesa[w] = 2; | |
| else if(mesa[x] == 2) mesa[w] = 1; | |
| if(!dfs(w)) return false; // visito ele, e checo se consigo colocar todos os seus amigos no lado correto | |
| // se não retorno false, se sim continuo. | |
| }else // se ja foi visitado | |
| { | |
| if(mesa[x] == mesa[w]) return false; // checo se estamos no mesmo lado da mesa, se sim retorno false, se não continuo | |
| } | |
| } | |
| return true; // se cheguei ate aqui, consegui colocar os amigos no lugar certo, retorno true. | |
| } | |
| int main() | |
| { | |
| int cont = 0; | |
| while(scanf("%d %d", &n, &m)!=EOF) | |
| { | |
| for(int i = 0 ; i < m ; ++i) // monto a lista de amigos | |
| { | |
| int u, v; | |
| scanf("%d %d", &u, &v); | |
| friends[u].push_back(v); | |
| friends[v].push_back(u); | |
| } | |
| bool ok = true; | |
| for(int j = 1 ; j <= n ; ++j) | |
| { | |
| if(!comp[j]) // chamo a DFS para todos os convidados | |
| { | |
| comp[j] = 1; | |
| mesa[j] = 1; | |
| if(!dfs(j)) // se não consegui colocar os amigos do lado certo | |
| { | |
| ok = false; // marco que não consegui | |
| break; // paro o loop | |
| } | |
| } | |
| } | |
| cont++; | |
| printf("Instancia %d\n", cont); | |
| if(ok){ // se consegui, imprimo sim | |
| printf("sim\n\n"); | |
| }else{ // caso contrário, imprimo nao | |
| printf("nao\n\n"); | |
| } | |
| // limpo as variáveis globais | |
| for(int i = 1 ; i <= n ; ++i) friends[i].clear(); | |
| memset(comp, 0, sizeof(comp)); | |
| memset(mesa, 0, sizeof(mesa)); | |
| } | |
| return 0; | |
| } |