754
poj 1093 Sorting It All Out AOV網絡+拓撲
一道拓撲的題，隻是每增加一條拓撲一次，要注意是否有人為添加的邊，也就是同一時刻有沒有多個可選項。
這題少加了個return 0，錯了n次……注意細節。
非常簡單的題，結果寫了70多分鍾……
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
bool vis[30];
int q[700];
int first[30],in[30],t[30];
int U[700],next[700],cnt;
int m,n;
void add(int v,int u)
{
in[u]++;
next[cnt]=first[v];
first[v]=cnt;
U[cnt++]=u;
}
char s[30];
int solve(int n)
{
memset(s,0,sizeof(s));
int top=-1,i,j,now,pos=0,c=0;
bool flag=1;
for(i=0;i<n;i++)//找到初始狀態
{
t[q[i]]=in[q[i]];
if(t[q[i]])continue;
t[q[i]]=top;top=q[i];
c++;
}
for(i=0;i<n;i++)
{
if(c>1) flag=0;//如果c>1，代表有人為添加的序列
else if(c==0)return -1;//存在環
s[pos++]=top+'A';
c--;
now=top;top=t[top];
for(j=first[now];j!=-1;j=next[j])
if(--t[U[j]]==0)
{
t[U[j]]=top;
top=U[j];
c++;
}
}
if(flag) return pos;
return 0;//少加了這個return 0，錯了n次……
}
bool input()
{
scanf("%d%d",&n,&m);
if(n==0&&m==0)return 0;
memset(first,-1,sizeof(first));
memset(in,0,sizeof(in));
memset(vis,0,sizeof(vis));
cnt=0;
int i,now=0,ans,pos,ff=0;
char so[5];
for(i=0;i<m;i++)
{
scanf("%s",so);if(ff)continue;
add(so[0]-'A',so[2]-'A');
if(vis[so[0]-'A']==0)
vis[so[0]-'A']=1,q[now++]=so[0]-'A';
if(vis[so[2]-'A']==0)
vis[so[2]-'A']=1;q[now++]=so[2]-'A';
ans=solve(now);//每增加一條一次拓撲
if(ans==-1){pos=i+1;ff=1;continue;}
else if(ans==n){ff=1;pos=i+1;continue;}
}
if(ans==n) printf("Sorted sequence determined after %d relations: %s.\n",pos,s);
else if(ans==-1) printf("Inconsistency found after %d relations.\n",pos);
else printf("Sorted sequence cannot be determined.\n");
return 1;
}
int main()
{
while(input());
}
最後更新：2017-04-02 00:06:54