混合图

                   (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]……

#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 %dn",u,v);
		else printf("%d %dn",v,u);
	}
//	while (1);
	return 0;
}