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:
| #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; | |
| } |

Comente