hdu 1285 토폴로지 정렬

13011 단어 HDU
요 며칠 KMP가 손쉽게 연습을 해서 선배가 또 토폴로지 서열을 만들었다. 작년에 토폴로지 서열을 제시했는데 연구가 없으니 먼저 코드를 붙여라!
전설에 의하면 토폴로지 서열이 누드 문제라고 하는데, 이상하게도 내가 처음으로 쓴 코드를 비교해 보니 느낌이 좋구나!왜 자꾸 와야 돼?나중에 아예 다시 한 번 썼어요.
WA 코드:
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 #define N 505
 6 int n,m;
 7 int match[N][N];
 8 int de[N];
 9 int main()
10 {
11     //freopen("input.txt","r",stdin);
12     //freopen("output.txt","w",stdout);
13 
14     while(scanf("%d%d",&n,&m)!=EOF)
15     {
16         memset(match,0,sizeof(match));
17         memset(de,0,sizeof(de));
18         int i,j;
19         for(i=0;i<m;i++)
20         {
21             int a,b;
22             scanf("%d%d",&a,&b);
23             match[a][b]=1;
24             de[b]++;
25         }
26         for(i=0;i<n;i++)
27         {
28 
29             for(j=1;j<=n;j++)
30                 if(de[j]==0)
31                     break;
32 
33             de[j]=-1;
34             if(i==n-1)
35                 printf("%d
",j); 36 else 37 printf("%d ",j); 38 int k; 39 for(k=1;k<=n;k++) 40 { 41 if(match[j][k]==1&&de[k]>0) 42 de[k]--; 43 } 44 } 45 } 46 return 0; 47 }

ac 코드:
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 #define N 505
 6 int d[N];
 7 int map[N][N];
 8 int n,m;
 9 int main()
10 {
11     while(scanf("%d%d",&n,&m)!=EOF)
12     {
13 
14         memset(map,0,sizeof(map));
15         memset(d,0,sizeof(d));
16         int i,j;
17         for(i=0;i<m;i++)
18         {
19 
20             int a,b;
21             scanf("%d%d",&a,&b);
22             if(map[a][b]==0)
23             {
24                 map[a][b]=1;
25                 d[b]++;
26             }
27         }
28         for(i=1;i<=n;i++)
29         {
30 
31             for(j=1;j<=n;j++)
32                 if(d[j]==0)
33                     break;
34             d[j]=-1;
35             if(i==n)
36                 printf("%d
",j); 37 else 38 printf("%d ",j); 39 for(int k=1;k<=n;k++) 40 41 if(map[j][k]==1&&d[k]>0) 42 d[k]--; 43 } 44 45 46 47 } 48 return 0; 49 50 }

우울하다

좋은 웹페이지 즐겨찾기