http://poj.org/problem?id=2337

用 G[u][weight] = v 存图,weight是排序后的字符串[i]的下标i

DFS这么写:(mxm是最大边数)

void dfs(int u)
{
    int v;
    For(v, mxm) if (!vis[v] && G[u][v])
    {
        vis[v] = true;
        dfs(G[u][v]);
        ans.PB(v);
    }
}
/*16ms,424KB*/

const int mx = 27;
const int mxm = 1000;

int G[mx][mxm]; /// 用 G[u][weight] = v 存图
int in[mx], out[mx];
bool vis[mxm];

vector<int> ans;
#define from first
#define to second

void init()
{
    mem(G, 0);
    mem(in, 0);
    mem(out, 0);
    mem(vis, 0);
}

bool ok(int &start) /// *有向图求道路, 先不判断连通性
{
    start = -1;
    int i, cnt1 = 0, cnt2 = 0, reserve;
    rForr(i, mx - 1, 1)
    {
        if (out[i]) reserve = i;
        if (in[i] != out[i])
        {
            if (in[i] == out[i] + 1) ++cnt1;
            else if (out[i] == in[i] + 1) ++cnt2, start = i;
            else return false;
        }
    }
    if (start == -1) start = reserve;
    return cnt1 <= 1 && cnt2 <= 1;
}

void dfs(int u)
{
    int v;
    For(v, mxm) if (!vis[v] && G[u][v])
    {
        vis[v] = true;
        dfs(G[u][v]);
        ans.PB(v);
    }
}

bool solve(int m)
{
    int start;
    if (!ok(start)) return false;
    ans.clear();
    dfs(start);
    return ans.size() == m;
}

string s[mxm];
map<string, int> mp;

int main()
{
    int t, m, i, u, v;
    SI(t);
    while (t--)
    {
        init();
        SI(m);
        For(i, m) cin >> s[i];
        sort(s, s + m);
        For(i, m)
        {
            u = s[i][0] & 31, v = s[i][s[i].size() - 1] & 31;
            G[u][i] = v, ++out[u], ++in[v];
        }
        if (!solve(m)) puts("***");
        else
        {
            rForr(i, ans.size() - 1, 1) cout << s[ans[i]], PC('.');
            cout << s[ans[0]], Pn();
        }
    }
    return 0;
}

Comments

comments powered by Disqus