SGU 101 修改

感谢这里。

test4确实是个不连通的case，奇怪的是我用check函数跟if (check() == false)来判断这个case，当不连通时就死循环，得到的结果是不一样的，前者得到WA，后者得到TLE，难道SGU能自动在某个条件下终止死循环，然后返回false吗。

不连通的情况FIX了，修改了代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <string.h>
using namespace std;

class Edge {
public:
    int no, u, v;
    char d;
    Edge reverse() {
        Edge rev;
        rev.no = no;
        rev.u = v;
        rev.v = u;
        rev.d = '-';
        return rev;
    }
};

class Graph {
private:
    map<int, int> u2i;
    vector<vector<Edge> > G;
    int deg[210], n, no, use[105], vUse[210];
    vector<Edge> solution;
public:
    Graph(vector<Edge>& edges) {
        n = edges.size();
        makeU2I(edges);
        memset(deg, 0, sizeof(deg));
        G.clear();
        G.resize(no);
        for (int i = 0; i < edges.size(); i++) {
            G[u2i[edges[i].u]].push_back(edges[i]);
            G[u2i[edges[i].v]].push_back(edges[i].reverse());
            deg[u2i[edges[i].u]]++;
            deg[u2i[edges[i].v]]++;
        }
    }
    void makeU2I(vector<Edge>& edges) {
        u2i.clear();
        for (int i = 0; i < edges.size(); i++) {
            u2i[edges[i].u] = u2i[edges[i].v] = 0;
        }
        no = 0;
        for (map<int, int>::iterator it = u2i.begin(); it != u2i.end(); it++) {
            it->second = no++;
        }
    }
    int solve() {
        int beg = -1, end = -1;
        for (int i = 0; i < no; i++) {
            if (deg[i] & 1) {
                if (beg == -1) {
                    beg = i;
                } else if (end == -1) {
                    end = i;
                } else {
                    return -1;
                }
            }
        }
        if (beg == -1) {
            beg = 0;
        }
        memset(use, 0, sizeof(use));
        dfs(beg);
        return 0;
    }
    bool dfs(int u) {
        for (int i = 0; i < G[u].size(); i++) {
            if (use[G[u][i].no] == 0) {
                use[G[u][i].no] = 1;

                if (dfs(u2i[G[u][i].v])) {
                    solution.push_back(G[u][i]);
                    return true;
                } else {
                    use[G[u][i].no] = 0;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            if (use[i] == 0) {
                return false;
            }
        }
        return true;
    }
    void check(int n) {
        if (solution.size() != n) {
            while (1);
        }
        for (int i = 0; i < solution.size() - 1; i++) {
            /*
            printf("%d %d, %d %d
", 
                solution[i].getU(), solution[i].getV(),
                solution[i + 1].getU(), solution[i + 1].getV());
                */
            
            //if (solution[i].getV() != solution[i + 1].getU()) {
            if (solution[i].v != solution[i + 1].u) {
                while (1);
            }
            
            
        }
    }
    bool check2(int n) {
        if (solution.size() != n) {
            while (1);
            return false;
        } else {
            return true;
        }
    }
    bool checkConnectity() {
        memset(vUse, 0, sizeof(vUse));
        vector<int> Q;
        Q.push_back(0);
        vUse[0] = 1;

        for (int i = 0; i < Q.size(); i++) {
            for (int j = 0; j < G[Q[i]].size(); j++) {
                if (vUse[u2i[G[Q[i]][j].v]] == 0) {
                    vUse[u2i[G[Q[i]][j].v]] = 1;
                    Q.push_back(u2i[G[Q[i]][j].v]);
                }
            }
        }

        for (int i = 0; i < no; i++) {
            if (vUse[i] == 0) {
                return false;
            }
        }
        return true;
    }
    void getSolution() {
        //for (int i = 0; i < solution.size(); i++) {
        for (int i = solution.size() - 1; i >= 0; i--) {
            printf("%d %c
", solution[i].no, solution[i].d);
        }
    }
};

int main()
{
    int n;
    scanf("%d", &n);

    vector<Edge> edges;
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);

        Edge e;
        e.no = i + 1;
        e.u = a; e.v = b;
        e.d = '+';

        edges.push_back(e);        
    }

    Graph graph(edges);
    if (graph.solve() == -1 || graph.checkConnectity() == false) {
        printf("No solution
");
    } else {
        graph.getSolution();
    }
    
    //system("pause");
}

上面的代码能处理自环的情况，可面临一个链上套了很多环的情况就会TLE，test 13应该就是这样的一个case。