HDU - 2647 토폴로지 정렬

이 문 제 는 행렬 로 표시 할 수 없습니다. 1w * 1w 는 절대 메모리 가 초과 되 고 데 이 터 를 분석 할 수 있 습 니 다. 앞의 a 의 돈 이 뒤의 b 보다 많 기 때문에 우 리 는 b 를 출 도, a 를 입도 로 해 야 합 니 다. 만약 에 이곳 을 모 르 면 예 를 들 어 b - > a - > c - > d, b 는 888 이 고 돈 수가 점점 올 라 가 야 합 니 다. 반대로 a 를 출 도 하면 문제 의 뜻 에 부합 되 지 않 습 니 다.
또 한 가지 주의해 야 할 점 이 있 습 니 다. 출력 - 1 의 상황 을 판단 할 때 입 도 를 0 으로 판단 할 수 없습니다. 중간 에 갈등 이 생 길 수 있 기 때 문 입 니 다. 예 를 들 어 a - > b - > c - > d - > c 는 입 도 를 0 으로 하 는 점 이 있 지만 출력 - 1;
 

#include<iostream>

#include<cstring>

#include<queue>

#include<cstdio>

using namespace std;

#define MAX 10005

int n,sum,ans;

int into[MAX],head[MAX],money[MAX];

struct Reward

{

    int to;

    int next;

} edge[2*MAX];

void topu()

{

    int i,j,l,v;

    queue<int>Q;

    for(i=1; i<=n; i++)

        if(into[i]==0)

            Q.push(i);//    0      

    while(!Q.empty())

    {

        v=Q.front();//      

        sum+=money[v];

        Q.pop();//  

        ans++; //              ，   n   

        for(l=head[v]; l!=-1; l=edge[l].next)//     v        

        {

            if(--into[edge[l].to]==0)//    -1 0，  v      

            {

                Q.push(edge[l].to);//      

                money[edge[l].to]=money[v]+1;//           1

            }

        }



    }

}

int main()

{

    int m,a,b,tot;

    while(scanf("%d%d",&n,&m)!=EOF)

    {



        memset(head,-1,sizeof(head));

        memset(into,0,sizeof(into));

        for(int i=1; i<=n; i++)

            money[i]=888;//        888

        tot=0;

        sum=0;

        ans=0;

        while(m--)

        {

            scanf("%d%d",&a,&b);//      ，     b    888，      

            edge[tot].to=a;

            edge[tot].next=head[b];

            head[b]=tot++;

            into[a]++;//    

        }

        topu();

        if(ans!=n)//          ，            

            sum=-1;

        cout<<sum<<endl;



    }



}