混合圖 (h[u]誤寫成h[q[u]]……）

                         混合圖
                   (dizzy.c/cpp/pas)
【問題描述】
    有一張N個點，M1條有向邊，M2條無向邊組成的混合圖。詢問一個給所有無向邊定向的方案。使得最終的圖中沒有環。保證一定有解。
【輸入格式】
    第一行，三個數字N,M1,M2。
    接下來M1+M2行，每行兩數字Ai,Bi。表示一條邊。
    前M1條是有向邊。方向是Ai到Bi。
【輸出格式】
    輸出M2行，按輸出順序輸出為無向邊確定的方向。Ai Bi或Bi Ai。
    有多解時輸出任意解。
【樣例輸入】
4 2 3
1 2
4 3
1 3
4 2
3 2
【樣例輸出】
1 3
2 4
2 3
【數據規模】
    1<=N<=100 000
    1<=M1,M2<=100000
 

拓撲排序即使有重邊也成立！
請務必注意哈希表h[u]別多套一個q[u]……

[cpp]
#include<cstdio> 
#include<cstring> 
#include<cmath> 
#include<cstdlib> 
#include<iostream> 
#include<functional> 
#include<algorithm> 
using namespace std; 
#define MAXN (100000+10) 
#define MAXM (100000+10) 
int n,m1,m2,indegree[MAXN]={0},head[MAXN],next[MAXM]={0},edge[MAXM]={0},tot=0; 
void addedge(int u,int v) 
{ 
    edge[++tot]=v; 
    next[tot]=head[u]; 
    head[u]=tot; 
} 
int q[MAXN*2]; 
bool b[MAXN]={0}; 
void topsort() 
{ 
    int head_=1,tail=0; 
    for (int i=1;i<=n;i++) 
        if (indegree[i]==0)  
        { 
            q[++tail]=i;b[i]=1; 
        } 
    while (head_<=tail) 
    { 
        int now=q[head_]; 
        int p=head[now]; 
        while (p) 
        { 
            int v=edge[p]; 
            indegree[v]--; 
            if (indegree[v]==0) 
            { 
                q[++tail]=v;b[v]=1; 
            }                                    
            p=next[p]; 
        }    
        head_++; 
    }                
} 
int h[MAXN]; 
int main() 
{ 
    freopen("dizzy.in","r",stdin); 
    freopen("dizzy.out","w",stdout); 
    scanf("%d%d%d",&n,&m1,&m2); 
    memset(head,0,sizeof(head)); 
    for (int i=1;i<=m1;i++) 
    { 
        int u,v; 
        scanf("%d%d",&u,&v); 
        addedge(u,v); 
        indegree[v]++; 
    } 
    topsort(); 
    for (int i=1;i<=n;i++)  
    { 
        h[q[i]]=i; 
    //  cout<<q[i]<<' '; 
    } 
/*  
    for (int i=1;i<=n;i++) cout<<q[i]<<' ';
    cout<<endl;
    for (int i=1;i<=n;i++) cout<<h[i]<<' ';
    cout<<endl;
*/   
    for (int i=1;i<=m2;i++) 
    { 
        int u,v; 
        scanf("%d%d",&u,&v); 
        if (h[u]<h[v]) printf("%d %d\n",u,v); 
        else printf("%d %d\n",v,u); 
    } 
//  while (1); 
    return 0; 
}