Posted on 2009-04-12 23:13
lzmagic 閱讀(1692)
評論(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.第一，要仔細看題，第二，還是要仔細看題。