第一題
#include<bits/stdc++.h>
using namespace std;

void killSubdivision(vector<vector<bool>> &graph){
    for(int i = 0 ; i < graph.size() ; i++){
        int num = 0;
        int a = -1, b = -1;
        for(int j = 0 ; j < graph.size() ; j++){
            if(graph[i][j] == true){
                if(a == -1){
                    a = j;
                }
                else if(a != -1 && b == -1){
                    b = j;
                }
                num++;
            }
            if(num > 2)
                break;
        }
        if(num == 2){
            for(int j = 0 ; j < graph.size() ; j++){
                if(i != j){
                    graph[i][j] = false;
                    graph[j][i] = false;
                }
            }
            graph[a][b] = true;
            graph[b][a] = true;
        }
    }
}

bool findK5(vector<vector<bool>> &graph){
    for(int a = 0 ; a < graph.size() ; a++){
        for(int b = 0; b < graph.size() ; b++){
            for(int c = 0 ; c < graph.size() ; c++){
                for(int d = 0; d < graph.size() ; d++){
                    for(int e = 0; e < graph.size() ; e++){
                        if(a != b && a != c && a != d && a != e && b != c && b != d && b != e && c != d && c != e && d != e)
                        if(graph[a][b] && graph[a][c] && graph[a][d] && graph[a][e] && graph[b][c] && graph[b][d] && graph[b][e] && graph[c][d] && graph[c][e] && graph[d][e]){
                            return true;
                        }
                    }
                }
            }
        }
    }
    return false;
}

bool findK33(vector<vector<bool>> &graph){
    for(int a = 0 ; a < graph.size() ; a++){
        for(int b = 0 ; b < graph.size() ; b++){
            for(int c = 0 ; c < graph.size() ; c++){
                for(int d = 0 ; d < graph.size() ; d++){
                    for(int e = 0 ; e < graph.size() ; e++){
                        for(int f = 0 ; f < graph.size() ; f++){
                            if(a != b && a != c && a != d && a != e && a != f && b != c && b != d && b != e && b != f && c != d && c != e && c != f && d != e && d != f && e != f)
                                if(graph[a][d] && graph[a][e] && graph[a][f] && graph[b][d] && graph[b][e] && graph[b][f] && graph[c][d] && graph[c][e] && graph[c][f]){
                                    return true;
                                }
                        }
                    }
                }
            }
        }
    }
    return false;
}

int main(){
    int Q;
    cin>>Q;
    for(int i = 0 ; i < Q ; i++){
        int n, m;
        cin>>n>>m;
        vector<vector<bool>> graph(n, vector<bool>(n, false));
        int u, v;
        for(int j = 0 ; j < m ; j++){
            cin>>u>>v;
            graph[u-1][v-1] = true;
            graph[v-1][u-1] = true;
        }
        killSubdivision(graph);
        if(findK5(graph)){
            cout<<"No\n";
            continue;
        }
        if(findK33(graph)){
            cout<<"No\n";
            continue;
        }
        cout<<"Yes\n";
    }

    return 0;
}


第二題
#include<bits/stdc++.h>
using namespace std;

struct Edge
{
    int src, dest;
};

struct Graph
{
    int V, E;
    Edge* edge;
};

struct subset
{
    int parent;
    int rank;
};
int find(struct subset subsets[], int i);
void Union(struct subset subsets[], int x, int y);

int kargerMinCut(struct Graph* GRAPH)
{
    struct Graph* graph = GRAPH;
    int V = graph->V, E = graph->E;
    Edge *edge = graph->edge;

    struct subset *subsets = new subset[V];

    for (int v = 0; v < V; ++v)
    {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    int vertices = V;

    while (vertices > 2)
    {
    int i = rand() % E;

    int subset1 = find(subsets, edge[i].src);
    int subset2 = find(subsets, edge[i].dest);

    if (subset1 == subset2)
        continue;
    else
    {
        vertices--;
        Union(subsets, subset1, subset2);
    }
    }

    int cutedges = 0;
    for (int i=0; i<E; i++)
    {
        int subset1 = find(subsets, edge[i].src);
        int subset2 = find(subsets, edge[i].dest);
        if (subset1 != subset2)
        cutedges++;
    }

    return cutedges;
}

int find(struct subset subsets[], int i)
{
    if (subsets[i].parent != i)
    subsets[i].parent =
            find(subsets, subsets[i].parent);

    return subsets[i].parent;
}

void Union(struct subset subsets[], int x, int y)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;

    else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

struct Graph* createGraph(int V, int E)
{
    Graph* graph = new Graph;
    graph->V = V;
    graph->E = E;
    graph->edge = new Edge[E];
    return graph;
}

int main()
{
    int V, E;
    cin>>V>>E;
    struct Graph* graph = createGraph(V, E);
    int u, v;
    for(int i = 0 ; i < E ; i++){
        cin>>u>>v;
        graph->edge[i].src = u-1;
        graph->edge[i].dest = v-1;
    }
    vector<int> cunt(100, 0);
    srand(time(NULL));
    for(int i = 0 ; i < 100 ; i++){
        cunt[kargerMinCut(graph)]++;
    }
    for(int i = 0 ; i < 100 ; i++){
        if(cunt[i] > 0){
            cout<<i;
            return 0;
        }
    }

    return 0;
}

第三題
#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int index;
    int from;
    int to;
    int weight;
    Edge(int a, int u, int v, int w):index(a), from(u), to(v), weight(w){};
};

int main(){
    int n, m;
    int u, v, w;
    cin>>n>>m;
    vector<vector<Edge>> adj(n);
    vector<Edge> pp;
    for(int i = 1 ; i <= m ; i++){
        cin>>u>>v>>w;
        adj[u-1].push_back(Edge(i, u-1, v-1 ,w));
        pp.push_back(Edge(i, u-1, v-1, w));
    }
    vector<bool> visited(n, false);
    vector<pair<unsigned int, int>> cost(n, pair<unsigned int, int>(3000000000, -1));
    cost[0] = {0, -1};
    int now = 0;
    while(visited[1] != true){
        int min = INT_MAX;
        for(int i = 1 ; i < cost.size() ; i++){
            if(visited[i] == false && cost[i].first < min){
                now = i;
            }
        }
        visited[now] = true;
        for(int i = 0 ; i < adj[now].size() ; i++){
            if(cost[adj[now][i].to].first > cost[now].first + adj[now][i].weight){
                cost[adj[now][i].to].first = cost[now].first + adj[now][i].weight;
                cost[adj[now][i].to].second = now;
            }
        }
    }
    int sp = cost[1].first;
    for(int i = 0 ; i < pp.size() ; i++){
        //cout<<endl<<i<<endl<<endl;
        vector<bool> Visited(n, false);
        vector<pair<unsigned int, int>> Cost(n, pair<unsigned int, int>(3000000000, -1));
        Cost[0] = {0, -1};
        now = 0;
        int U = pp[i].from;
        int V = pp[i].to;
        int W = pp[i].weight;
        for(int j = 0 ; j < n ; j++){
            int min = INT_MAX;
            //for(int i = 0 ; i < Cost.size() ; i++)cout<<Cost[i].first<<" ";
            for(int i = 1 ; i < Cost.size() ; i++){
                if(Visited[i] == false && Cost[i].first < min){
                    now = i;
                }
            }
            Visited[now] = true;
            //cout<<endl<<now;
            //cout<<endl<<U;
            for(int i = 0 ; i < adj[now].size() ; i++){
                if(now != U || adj[now][i].to != V)
                if(Cost[adj[now][i].to].first > Cost[now].first + adj[now][i].weight){
                    Cost[adj[now][i].to].first = Cost[now].first + adj[now][i].weight;
                    Cost[adj[now][i].to].second = now;
                }
            }
            if(now == V){
                if(Cost[U].first > Cost[V].first + W){
                    Cost[U].first = Cost[V].first + W;
                    Cost[U].second = V;
                }
            }

        }
        //cout<<sp<<endl;
        //cout<<Cost[1].first<<endl;
        if(Cost[1].first < sp)
            cout<<"HAPPY\n";
        else if(Cost[1].first == sp)
            cout<<"SOSO\n";
        else
            cout<<"SAD\n";
    }

    return 0;
}