虽然这个问题弱到丢人但还是想问问。 以下是我的代码,有许多调试的代码。且抛开正确性。第一个样例中,按理说我用来存节点的数组p里有1,2,分别对应A,B。而在71行和73行中,我输出p[2],第一次是2第二次是1.但我看中间那一行代码······不明白问题出在那里。
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edges{
int to,nxt;
}edge[1000];
int hd[27],idx,in[27],out[27],in2[27],out2[27],a[27],flag,nump,p[27],vis[27];
void add(int a,int b)
{
edge[++ idx].to = b,edge[idx].nxt = hd[a],hd[a] = idx;
}
queue<int> q;
void toposort(int x,int nump)
{
int cnt = 0;
for(int i = 1;i <= nump;++ i)
if(in2[p[i]] == 0)
{
q.push(p[i]);
printf("p[i] : %d\n",p[i]);
a[++ cnt] = p[i];
}
while(!q.empty())
{
int num = q.front();q.pop();
for(int i = hd[num];i;i = edge[i].nxt)
{
int v = edge[i].to;
-- in[v];
if(!in[v])
{
q.push(v);
a[++ cnt] = v;
}
}
}
printf("cnt : %d\n",cnt);
if(cnt == n)//第一种情况
{
printf("Sorted sequence determined after %d relations: ",x);
for(int i = cnt;i > 0;-- i)
printf("%c",char(a[cnt] - 1 + 'A'));
printf(".");flag = 1;
return;
}else if(cnt < nump)
{
printf("Inconsistency found after %d relations.",x);
flag = 1;
return;
}else if(x == m){//最后一次才判
printf("Sorted sequence cannot be determined.");
flag = 1;
return ;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;++ i)
{
char a,b,c;int A,B;
cin >> a;c = getchar();cin >> b;
A = int(a - 'A' + 1);B = int(b - 'A' + 1);
if(!vis[A]){
vis[A] = 1;p[++ nump] = A;
}
if(!vis[B]){
vis[B] = 1;p[++ nump] = B;
}
printf("nump : %d\n",nump);
cout << p[2] << endl;
add(b,a);++ in[a];++ out[b];in2[a] = in[a];out2[b] = out[b];
cout << p[2] << endl;
for(int i = 1;i <= nump;++ i)
printf("i : %d in2[i] : %d out2[i] : %d\n",p[i],in2[p[i]],out2[p[i]]);
toposort(i,nump);
if(flag)return 0;
}
return 0;
}