BC DZY Loves Topological Sorting

DZY Loves Topological Sorting  
 Accepts: 112
 
 Submissions: 586
 Time Limit: 4000/2000 MS (Java/Others)
 
 Memory Limit: 131072/131072 K (Java/Others)
문제 설명

                   ，            
    
     (u→v)
       
    
     u
       
    
     v
    ，   
    
     u
           
    
     v
      。
  ，DZY        (DAG)。       
    
     k
        ，            。

입력 설명

       。 (
    
     TestCase≤5
    )
   ，      
    
     n,m,k(1≤n,m≤105,0≤k≤m)
    .
   
    
     m
     ，        
    
     u,v(u≠v,1≤u,v≤n)
    ,        
    
     (u→v)
    .

출력 설명

        ，              。

입력 샘플

5 5 2
1 2
4 5
2 4
3 4
2 3
3 2 0
1 2
1 3

출력 샘플

5 3 1 2 4
1 3 2

Hint

  1.   (2->3),(4->5)   ，              ：(5,3,1,2,4).

   ：        

방법 2: vector 저장 변 사용

#include <bits/stdc++.h>

using namespace std;
#define maxn 100000 + 10
#define INF 0x7ffffff
#define Lson L, mid, root<<1
#define Rson mid+1, R, root<<1|1

int Min[maxn<<2];
int deg[maxn];
int n, m, k, cnt, num;
int head[maxn];
vector<int> vec;

///                    

struct Edge
{
    int v;
    int next;
} edge[maxn];

void init()
{
    num = 0;
    cnt = 0;
    memset(head, -1, sizeof(head));
    memset(deg, 0, sizeof(deg));
    vec.clear();
    int u, v;
    for(int i=0; i<m; i++)
    {
        cin>>u>>v;
        deg[v]++;
        edge[cnt].v = v;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }
}

void Pushup(int root)
{
    Min[root] = min(Min[root<<1] , Min[root<<1|1]);
}

void Bulid(int L, int R, int root)
{
    if(L == R)
    {
        Min[root] = deg[++num];
        return;
    }
    int mid = (L+R)>>1;
    Bulid(Lson);
    Bulid(Rson);
    Pushup(root);
}

void Update(int q, int Deg, int L, int R, int root)
{
    if(L == R)
    {
        Min[root] = Deg;
        return ;
    }
    int mid = (L+R)>>1;
    if(q <= mid) Update(q, Deg, L, mid, root<<1);
    else Update(q, Deg, mid+1, R, root<<1|1);
    Pushup(root);
}

///  Min    k   
int Query(int L, int R, int root)
{
    if(L==R && Min[root]<=k) return L;
    int mid = (L+R)>>1;
    if(Min[root<<1|1] <= k)
        return Query(Rson);
    else return Query(Lson);
}

void topo()
{
    for(int i=1; i<=n; i++)
    {
        int id = Query(1, n, 1);
        vec.push_back(id);
        k -= deg[id];
        deg[id] = INF;
        Update(id, INF, 1, n, 1);
        for(int j=head[id]; j!=-1; j=edge[j].next)
        {
            int v = edge[j].v;
            deg[v]--;
            Update(v, deg[v], 1, n, 1);
        }
    }
}

int main()
{
    while(~scanf("%d%d%d", &n, &m, &k))
    {
        init();
        Bulid(1, n, 1);
        topo();
        for(int i=0; i<vec.size(); i++)
        {
            cout<<vec[i];
            if(i != vec.size()-1) cout<<" ";
            else cout<<endl;
        }
    }
    return 0;
}