我把第一个测试点下载下来了,本地测也过了,但是一交全RE有没有大佬帮忙看看
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<vector>
#pragma warning(disable:4996)
using namespace std;
int n, m, f[300], sizef[300], fls, tot, head[300], in[300];
bool vis[300], vist[300];
bool flag = false;
vector<int> vc;
struct node
{
int v, nt;
}edge[6010];
int find(int x) {
if (f[x] == x) return x;
else return f[x] = find(f[x]);
}
void build(int x, int y) {
int xx = find(x), yy = find(y);
if (xx != yy) {
f[xx] = yy;
}
}
void add(int u, int v) {
edge[++tot].v = v;
edge[tot].nt = head[u];
head[u] = tot;
in[v]++;
}
bool dfs(int x) {
for (int i = head[x]; i; i = edge[i].nt) {
//cout << edge[i].v << " " << vis[edge[i].v] << endl;
if (vis[edge[i].v]) {
return true;
}
if (!vist[edge[i].v]) {
vist[edge[i].v] = true;
vis[edge[i].v] = true;
if (dfs(edge[i].v)) {
return true;
}
vis[edge[i].v] = false;
}
}
return false;
}
void vec(int x) {
vis[x] = true;
for (int i = head[x]; i; i = edge[i].nt) {
bool pd = false;
if (vis[edge[i].v]) continue;
for (vector<int>::iterator it = vc.begin(); it != vc.end(); ++it) {
if (*it == edge[i].v) {
pd = true;
break;
}
}
if (pd) continue;
vector<int>::iterator it;
int j;
for (j = 0; j < vc.size(); ++j) {
if (vc[j] == x) {
++j;
vc.insert(vc.begin() + j, edge[i].v);
break;
}
}
//vc.push_back(edge[i].v);
vec(edge[i].v);
}
}
int main() {
scanf("%d%d", &n, &m);
char a, b, c;
for (int i = 0; i <= 26; ++i) {
f[i] = i;
}
for (int i = 1; i <= m; ++i) {
memset(sizef, 0, sizeof(sizef));
memset(vis, false, sizeof(vis));
memset(vist, false, sizeof(vist));
scanf("%c", &a);
scanf("%c%c%c", &a, &b, &c);
int at = a - 'A';
int ct = c - 'A';
build(at, ct);
if (b == '>') add(ct, at);
else add(at, ct);
for (int j = 0; j < 26; ++j) {
if (!vist[j]) {
vis[j] = true;
vist[j] = true;
if (dfs(j)) {
printf("Inconsistency found after %d relations.", i);
return 0;
}
vis[j] = false;
}
}
if (flag) continue;
memset(vis, 0, sizeof(vis));
for (int j = 0; j < 26; ++j) {
if (!in[j] && head[j]) {
vc.push_back(j);
vec(j);
break;
}
}
if (vc.size() == n) {
flag = true;
fls = i;
}
else {
while (vc.size()) {
vc.pop_back();
}
}
}
if (vc.size() != n) {
printf("Sorted sequence cannot be determined.");
return 0;
}
else {
printf("Sorted sequence determined after %d relations: ", fls);
for (vector<int>::iterator it = vc.begin(); it != vc.end(); ++it) {
printf("%c", 'A' + *it);
}
printf(".");
}
return 0;
}
思路挺简单就是代码有点复杂