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

补充：软件开发 , C++ ,