#include<stdio.h>
#include<string.h>
int in[5000];
char map[3000][3000];
int n;
int panduan()
{
int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(map[i][j]=='1')
in[j]++;
for(i=0;i<n;i++)
{
j=0;
while(in[j]!=0)
j++;
if(j==n)
return 0;
else
{
in[j]--;
for(k=0;k<n;k++)
if(map[j][k]=='1')
in[k]--;
}
}
return 1;
}
int main()
{
int t,i,r;
scanf("%d",&t);
r=1;
while(t--)
{
scanf("%d",&n);
memset(in,0,sizeof(in));
getchar();
for(i=0;i<n;i++)
{
scanf("%s",map[i]);
}
printf("Case #%d: ",r++);
if(panduan())
printf("No\n");
else
printf("Yes\n");
}
return 0;
}
拓撲排序什麼是拓撲序列
通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。離散數學中關於偏序和全序的定義：
若集合X上的關系是R,且R是自反的、反對稱的和傳遞的，則稱R是集合X上的偏序關系。
設R是集合X上的偏序（Partial Order）,如果對每個x,y屬於X必有xRy 或 yRx，則稱R是集合X上的全序關系。
比較簡單的理解：偏序是指集合中只有部分成員可以比較，全序是指集合中所有的成員之間均可以比較。
注意：
①若將圖中頂點按拓撲次序排成一行，則圖中所有的有向邊均是從左指向右的。
②若圖中存在有向環，則不可能使頂點滿足拓撲次序。
③一個DAG的拓撲序列通常表示某種方案切實可行。
一般應用：
拓撲排序常用來確定一個依賴關系集中，事物發生的順序。例如，在日常工作中，可能會將項目拆分成A、B、C、D四個子部分來完成，但A依賴於B和D，C依賴於D。為了計算這個項目進行的順序，可對這個關系集進行拓撲排序，得出一個線性的序列，則排在前面的任務就是需要先完成的任務。
實現的基本方法
拓撲排序方法如下:
(1)從有向圖中選擇一個沒有前驅(即入度為0)的頂點並且輸出它.
(2)從網中刪去該頂點,並且刪去從該頂點發出的全部有向邊.
(3)重復上述兩步,直到剩余的網中不再存在沒有前趨的頂點為止.
編輯本段
拓撲序列 Pascal代碼在計算機語言中的應用：program TopSort;var
map,link:array [1..100,1..100] of integer;
v,pnt:array [1..100] of integer;
n,m,a,b,i,j,k:integer;
begin
fillchar(map,sizeof(map),0);
fillchar(link,sizeof(link),0);
fillchar(v,sizeof(v),0);
readln(n,m);
for i:=1 to m do
begin
readln(a,b);
map[a,b]:=1;
v[b]:=v[b]+1;
end;
i:=0;
link:=map;
while (i<n) do
begin
j:=1;
while (v[j]<>0) do inc(j);
v[j]:=-1;
for k:=1 to n do
if link[j,k]=1 then begin dec(v[k]);link[j,k]:=0; end;
inc(i);
pnt[i]:=j;
end;
for i:=1 to n do
writeln(pnt[i]);
end.
拓撲序列 C++核心代碼
bool TopologicalSort(int a[][101]) //可以完成拓撲排序則返回True
{
int n = a[0][0], i, j;
int into[101], ans[101];
memset(into, 0, sizeof(into));
memset(ans, 0, sizeof(ans));
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (a[i][j] > 0)
into[j]++;
}
}
into[0] = 1;
for (i = 1; i <= n; i++)
{
j = 0;
while (into[j] != 0)
{
j++;
if (j > n)
return false;
}
ans[i] = j;
into[j] = -1;
for (int k = 1; k <= n; k++)
{
if (a[j][k] > 0)
into[k]--;
}
}
for (i = 1; i <= n; i++)
{
cout << ans[i] << " ";
}
cout << endl;
return true;
}
延伸 拓撲學
拓撲學是近代發展起來的一個研究連續性現象的數學分支。中文名稱起源於希臘語Τοπολογία的音譯。Topology原意為地貌，於19世紀中期由科學家引入，當時主要研究的是出於數學分析的需要而產生的一些幾何問題。發展至今，拓撲學主要研究拓撲空間在拓撲變換下的不變性質和不變量。
