noic-solucao-intermediario-s56.cpp

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