這兩天看拓?fù)渑判颍珹題很不順利，桑心啊，桑心啊~~
題意描述：
N個(gè)人參加比才，給出M組兩個(gè)隊(duì)員之間的勝負(fù)情況，要求輸出總體的比賽名次。如果有多種情況，輸出字典序最小的那組結(jié)果。
拓?fù)渑判騾㈤啠?a href="http://www.shnenglu.com/hoolee/archive/2012/08/16/187400.html">http://www.shnenglu.com/hoolee/archive/2012/08/16/187400.html
以下是本題代碼；
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 510
int N, M;
int mp[LEN][LEN];
int indgr[LEN];
int s[LEN];
int list[LEN];
int lstlen;
int findZeroIndgr()
{
int i;
for(i = 0; i < N; i++)
if(s[i] == 0 && indgr[i] == 0)
return i;
}
void Topological()
{
int i, j;
int zr;
for(i = 0; i < N; i++)
{
zr = findZeroIndgr();
s[zr] = 1;
list[lstlen++] = zr;
for(j = 0; j < N; j++)
if(mp[zr][j] == 1)
indgr[j]--;
}
}
int main()
{
int i, j;
int p1, p2;
while(scanf("%d%d", &N, &M) != EOF)
{
memset(mp, 0, sizeof(mp));
memset(indgr, 0, sizeof(indgr));
memset(s, 0, sizeof(s));
for(i = 0; i < M; i++)
{
scanf("%d%d", &p1, &p2);
p1--;
p2--;
if(mp[p1][p2] == 0)
{
mp[p1][p2] = 1;
indgr[p2]++;
}
}
lstlen = 0;
Topological();
int gard = 0;
for(i = 0; i < lstlen; i++)
if(gard++ != 0)
printf(" %d", list[i] + 1);
else
printf("%d", list[i] + 1);
putchar(10);
}
//system("pause");
}
posted on 2012-08-18 17:17
小鼠標(biāo) 閱讀(242)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
圖論