有数据的话可以给一个吗？
by amsterdam @ 2018-05-12 10:46:35
二分提交法找到错误了，在
```cpp
graph[u].push_back(v);
```
有大神能解释一下为什么吗？
by amsterdam @ 2018-05-12 10:56:08
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define REG register
#define max(a,b) a>b?a:b
#define min(a,b) a>b?b:a
#define E() putchar(10)
using namespace std;
const int maxn=1e4+3;
const int inf=0x3f3f3fll;
typedef long long ll;
int n,m,into[maxn],head[maxn],ans[maxn],chd[maxn],t=0;
bool pd[maxn][maxn],vis[maxn];//pd[i][j]=1,表示i>j;
queue<char> ANS;
struct Edge{
int v,next;
}s[maxn];
inline void add(REG int u,REG int v,REG int p)
{
s[p]=(Edge){v,head[u]};
head[u]=p;
return;
}
inline void Floyd()
{
for(REG int k=1;k<=n;k++)
{
for(REG int i=1;i<=n;i++)
{
for(REG int j=1;j<=n;j++)
{
pd[i][j]|=pd[i][k]&pd[k][j];
}
}
}
return;
}
inline void topsort()
{
queue<int> que;
int pd=0,num=0;
for(REG int i=1;i<=n;i++)
if(!into[i])
{
num++;
if(num>1) pd=1;
que.push(i);
}
while(!que.empty())
{
num=0;
int x=que.front();
que.pop();
ANS.push(x);
for(REG int i=head[x];i;i=s[i].next)
{
int to=s[i].v;
into[to]--;
t=max(t,i);
if(!into[to])
{
que.push(to),num++;
if(num>1) pd=1;
}
}
}
if(pd) printf("Sorted sequence cannot be determined.\n");
else
{
printf("Sorted sequence determined after %d relations: ");
while(!ANS.empty()) putchar(ANS.front()+64),ANS.pop();
putchar('.');
}
}
int main()
{
scanf("%d %d",&n,&m);
char ptr[8];
for(REG int i=1;i<=m;i++)
{
scanf(" %s",ptr+1);
int u=ptr[1]-64,v=ptr[3]-64;
if(pd[v][u]||u==v){printf("Inconsistency found after %d relations.\n",i);return 0;}
pd[u][v]=1;
add(u,v,i);
into[v]++;
Floyd();
topsort();
}
puts("Sorted sequence cannot be determined.\n");
return 0;
}
```
by Explorer_CYC @ 2018-05-15 18:54:23
我又来了。。。
换了一种写法，这次全WA
qwq
```
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=28;
const int inf=1<<30;
struct edge{
int v;
edge *next;
}pool[maxn*maxn],*head[maxn];
int top=0;
int rudeg[maxn];
int n,m;
bool vis[maxn];
int size=0;
queue <int>ans;
void addedge(int u,int v){
edge *temp=&pool[top++];
temp->v=v;
temp->next=head[u];
head[u]=temp;
rudeg[v]++;
if(vis[u]==false)size++,vis[u]=true;
if(vis[v]==false)size++,vis[v]=true;
}
bool topsort(){
int ru[maxn];
for(int i=1;i<=n;i++)ru[i]=rudeg[i];//<--------------------***
while(ans.empty()==false)ans.pop();
bool used[30];
int left=size;
queue<int>que;
for(int i=1;i<=maxn;i++){
used[i]=false;
}
for(int i=1;i<=n;i++){
if(ru[i]==0 && vis[i]==true)
que.push(i),used[i]=true;
}
while(que.empty()==false){
int u=que.front();
ans.push(u);
left--;
que.pop();
for(edge *i=head[u];i;i=i->next){
ru[i->v]--;
if(ru[i->v]==0 && vis[i->v]==true && used[i->v]==false)
que.push(i->v);
}
}
if(left!=0)return false;
return true;
}
int main(){
scanf("%d%d",&n,&m);getchar();
for(int i=1;i<=n;i++)head[i]=NULL,vis[i]=false;
for(int i=1;i<=maxn*maxn;i++)pool[i].v=0;
for(int i=1;i<=m;i++){
char u,v;
if(u==v)printf("Inconsistency found after %d relations.\n",i);
scanf("%c<%c",&u,&v);getchar();
addedge(u-'A'+1,v-'A'+1);
bool t=topsort();
if(t==true){
if(size!=n)continue;
printf("Sorted sequence determined after %d relations: ",i);
while(ans.empty()==false){
printf("%c",'A'+ans.front()-1);
ans.pop();
}
printf(".\n");
return 0;
}
else{
printf("Inconsistency found after %d relations.\n",i);
return 0;
}
}
printf("Sorted sequence cannot be determined.\n");
return 0;
}
```
by amsterdam @ 2018-09-22 11:13:20