SRM 693 div2 easy TriangleEasy

問題

問題概要

グラフが与えられる。そのグラフの中に三角形を作る。最小でいくつの辺を加えればできるか。

解法

まず、辺が1つもなければ、必要な最小の辺の数は3となる。次に辺がある場合を考える。u - v　の辺がある場合を考える。このとき、u - x(xはvではない)辺が存在すれば、辺を加える数は1つでよくなる。同様にv - y(yはuではない)辺が存在すれば、辺を加える数も1つでよくなる。そして、x = yとなるものが存在すれば、すでに三角形はできているので、加える辺の最小数は0ということになる。
5角形の閉路検出

No.408 五輪ピック - yukicoder

ミス

はじめは、dfsで探索しようと思って書いたけど、なんかうまくいかない。

コード

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

bool G[55][55];
class TriangleEasy{
public:

    int find(int n, vector <int> x, vector <int> y){
        rep(i, 55)rep(j, 55) G[i][j] = false;
        for (int i = 0; i < x.size(); ++i){
            int u = x[i], v = y[i];
            G[u][v] = true;
            G[v][u] = true;
        }

        bool flag1 = false;
        bool flag2 = false;
        rep(u, n)rep(v, n){
            if(u == v) continue;
            /*
                 w
                / \
               u - v
            */
            if(G[u][v]){//u - vに辺がある
                rep(w, n){
                    if(u == w || v == w) continue;
                    if(G[w][u] && G[w][v]) flag2 = true;
                    else if(G[w][u] || G[w][u]) flag1 = true;
                }
            }
        }

        if(x.size() == 0 || y.size() == 0) return 3;
        else if(flag2) return 0;
        else if(flag1) return 1;
        else return 2;
    }
};