混合图 (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; 
}