Posted on 2009-04-12 23:13
lzmagic 阅读(1633)
评论(5) 编辑 收藏 引用 所属分类:
OJ
wa了很多次，终于过了，咔咔~笑一下先。
第一次很快用拓扑排序把代码敲出来，提交，wa，仔细分析后，发现忽略了重复边的情况，插入边(u, v)，如果图g已经存在了边(u,v)，就不能再增加v的入度。
很快改过来，提交，还是wa，很无奈，上网看看大牛评论，原来是只要当前输入数据能“确定唯一”，及时后面输入数据“有环”，也是判定为“确定唯一”。也就是说，每输入一条边，如果判定有结果，忽略后面输入数据，即使后面输入数据能改变结果。
再改，再提交，还是wa，几度欲放弃之，还是坚持下来了，上google找别人代码来分析，结果发选只要当前输入数据“有环”，及时当前输入数据“不能确定唯一”，也是判定为“有环”。
把判定顺序改过后，提交，终于ac!!!
呼~~~爽YY中……
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
#include <ctime>
#include <cstdlib>
#include <cctype>
using namespace std;
#define UNSURE 0 // 不能确定
#define CYCLED 1 // 存在回路
#define SORTED 2 // 已经排序
int n; // n ：顶点个数
vector<list<int> > g; // g ：图
vector<int> top; // top ：拓扑序列
vector<int> ins; // ins ：入度
int Topsort()
{
bool unsure(false);
queue<int> que;
vector<int> cnt(ins.begin(), ins.end()); // 用cnt存储ins，避免修改ins。
for (int j = 0; j < n; ++j)
if (cnt[j] == 0) que.push(j); // 入度为0的顶点入队。
int u;
list<int>::iterator it;
top.clear();
while (!que.empty())
{
if (que.size() != 1) unsure = true; // 如果选择顶点多余1个，不能确定。
u = que.front(); que.pop();
top.push_back(u);
for (it = g[u].begin(); it != g[u].end(); ++it)
if (--cnt[*it] == 0) que.push(*it);
}
if (top.size() != n) return CYCLED; // 先判断是否有环，即使不能确定，
if (unsure) return UNSURE; // 再判断是否不能确定。
return SORTED;
}
int main()
{
int steps, ans;
string exp;
int m, u, v, i;
while (cin >> n >> m, n != 0 || m != 0) // 2 <= n <= 26
{
g.assign(n, list<int>());
ins.assign(n, 0);
ans = UNSURE;
for (steps = 0; ans == UNSURE && steps < m; ++steps)
{
cin >> exp;
u = int(exp[0] - 'A'), v = int(exp[2] - 'A');
if (find(g[u].begin(), g[u].end(), v) == g[u].end()) // 如果不存在边(u, v)，添加。
g[u].push_back(v), ++ins[v];
ans = Topsort();
}
for (i = steps; i < m; ++i) cin >> exp; // 处理剩下无用的输入数据。
if (ans == UNSURE) // Output()
cout << "Sorted sequence cannot be determined." << endl;
else if (ans == CYCLED)
cout << "Inconsistency found after " << steps << " relations." << endl;
else
{
cout << "Sorted sequence determined after " << steps << " relations: ";
for (i = 0; i < n; i++) cout << char('A' + top[i]);
cout << "." << endl;
} // end Output()
}
system("pause");
return 0;
}
ps.第一，要仔细看题，第二，还是要仔细看题。