Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM ICPC 2018 World Finals

## kahn写的，需要判断是否有环和是否唯一

Posted by 2016150119 at 2017-10-29 13:05:41 on Problem 1094
```#include<cstdio>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cassert>
#include<vector>
#include<deque>
#include<list>
#include<set>
#include<map>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

const int MAXN = 30 + 10;
const int INF_MAX = 1 << 28;
const double INF_MIN = 1e-8;

int n, m;
int edge[MAXN][MAXN];

bool input() {
cin >> n >> m;
if (n == 0 && m == 0) {
return false;
}
memset(edge, 0, sizeof(edge));
return true;
}

void kahn(int &idx, int *ans, bool &hasHuan, bool &isWeiYi) {
int *degree = new int[n];
memset(degree, 0, n * sizeof(n));
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
degree[j] += edge[i][j];
}
}

queue<int> q;
for (int i = 0; i < n; i++) {
if (degree[i] == 0) {
q.push(i);
}
}

isWeiYi = true;
idx = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
ans[idx++] = u;
if ((int)q.size() != 0) {
isWeiYi = false;
}

for (int j = 0; j < n; j++) {
if (edge[u][j] == 1) {
degree[j]--;
if (degree[j] == 0) {
q.push(j);
}
}
}
}

hasHuan = idx < n;
}

void solve() {
int idx;
int *ans = new int[n];
bool isEnd = false;

for (int i = 1; i <= m; i++) {
char c1, tmp, c2;
cin >> c1 >> tmp >> c2;
edge[c1 - 'A'][c2 - 'A'] = 1;

if (isEnd) {
continue;
}

bool hasHuan;
bool isWeiYi;
kahn(idx, ans, hasHuan, isWeiYi);
if (hasHuan) {
cout << "Inconsistency found after ";
cout << i << " relations.\n";
isEnd = true;
continue;
}
if (!hasHuan && isWeiYi) {
cout << "Sorted sequence determined after ";
cout << i;
cout << " relations: ";
for (int i = 0; i < idx; i++) {
cout << (char)(ans[i] + 'A');
}
cout << ".\n";
isEnd = true;
continue;
}
}
if (!isEnd) {
cout << "Sorted sequence cannot be determined.\n";
}
}

int main()
{
//freopen("input.cpp", "r", stdin);///
//freopen("output.cpp", "w", stdout);///

while (input()) {
solve();
}

return 0;
}
```

Followed by: