OpenJudge

lijinyu

  • 常艺胧
    常艺胧 17天前 回复

    #include<bits/stdc++.h>
    using namespace std;
    #define MAXN 10005
    //bool graph[maxn][maxn] = {{ false }};
    //int Count[maxn] = { 0 };
    int v,a;
    struct Vtx {
    int To; Vtx *Next;
    Vtx(void) : To(-1), Next(NULL) {}
    };

    struct VtxHead : Vtx {
    int InDegree;
    Vtx *Head;

    void operator += (int To)
    {
    if (!Head) {
    Next = new Vtx();
    Next->To = To;
    Head = Next;
    } else {
    Next->Next = new Vtx();
    Next = Next->Next;
    Next->To = To;
    }
    }

    VtxHead(void) :
    Head(NULL), InDegree(0) {}
    } Graph[MAXN];

    struct Unit{
    int x;
    bool operator < (const Unit &y) const
    { return x > y.x;}
    };
    inline void topsort(){
    priority_queue<Unit> travel;
    for(int i = 1 ; i <= v ; i++)
    {
    if(Graph[i].InDegree == 0)
    travel.push(Unit{ i });
    }
    while (!travel.empty())
    {
    int Crtidx = travel.top().x;
    travel.pop();
    cout<<"v"<<Crtidx<<" ";
    for(Vtx *i = Graph[Crtidx].Head;
    i; i = i ->Next)
    if(--Graph[i->To].InDegree == 0)
    travel.push(Unit{i->To});
    }
    }
    int main()
    {
    cin>>v>>a;
    for(int i = 1 ; i <= v; ++i)
    Graph[i].To = i;

    for(int i = 1; i <= a; ++i)
    {
    int x,y;
    cin>>x>>y;

    Graph[x] += y;
    Graph[y] += x;

    ++Graph[y].InDegree;
    }
    topsort();
    return 0;
    }

想要评论吗?

注册OpenJudge账号,如果您已经注册,请先登入