1248: 游乐园Pleasure Ground

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 6  Solved: 2
[Submit][Status][Discuss]

Description

HarryPotter是一家游乐场的新负责人。刚上任时HarryPotter发现游客们频频抱怨 游乐场的道路非常拥挤。经过研究,HarryPotter打算把游乐场中所有道路改为单行道, 就是说游客只能从道路的一端走到另一端,而反过来不行。但是新的问题出现了:如何 保证游客能从公园的任意一个的地方走到任意其他地方。由于游乐场的道路错综复杂, HarryPotter花了很长时间也没找到道路更改的方案。 整个游乐场可以看作是由n个区域和m个连接两区域的道路组成的。任意两个不同的 区域间至多有一条道路。请你帮助HarryPotter将所有道路设为单向,并且使游客能从 任意区域到达任何他想去的区域。

Input

第一行有2个整数n,m。n为游乐场被的区域数,m为道路数。 以下有m行,每行有两个整数i,j。表示区域i与区域j之间有一条道路。 规模:0

Output

如果没有可行方案就输出"impossible",否则: 输出m行,每行有两个整数i,j,表示区域i与区域j之间的道路方向为从i到j。 注意:输出数据描述的道路必须与输入数据吻合。也就是说对于输入数据中的每一 组i,j,一定能在输出数据件中找到i,j或j,i。

Sample Input

输入样例1
3 3
1 2
1 3
2 3
输入样例2
4 3
1 2
2 3
3 4

Sample Output

输出样例1
1 2
2 3
3 1

输出样例2
impossible

 

题目链接:

    http://www.lydsy.com/JudgeOnline/problem.php?id=1248

Solution

    如果要每个点都能到达其他所有点,那么对于第1个点就要能到达所有点。。。

    然后每个点都要能到达第1个点。。。。

    于是第一次DFS,把每条可以连到新点的线方向确定下来。。

    因为对于有向图来说,每个点都在环上才能满足题意。。所以第一次深搜宽度越小越好。。

    去掉所有边,把方向确定的边连反向边,其他边重连双向边。。

    再做一次DFS。。。把每条必需确定方向的边确定掉。。

    两次DFS如果又一次到不了某个点,就是无解。。。

    其他未确定方向的边就随便啦。。。。

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define N 200000
#define LL long long
using namespace std;
inline int Read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,cnt=0;
int hed[N],vis[N];
struct LINE{
int l,r,c;
}L[1000000];
struct edge{
int r,num,nxt;
}e[2000000];
void insert(int u,int v,int num){
e[++cnt].r=v;e[cnt].num=num;e[cnt].nxt=hed[u];hed[u]=cnt;
}
void dfs1(int x){
vis[x]=1;
for(int i=hed[x];i;i=e[i].nxt)
if(vis[e[i].r]==0){
if(e[i].r==L[e[i].num].r) L[e[i].num].c=1;
else L[e[i].num].c=2;
dfs1(e[i].r);
}
}
void dfs2(int x){
vis[x]=1;
for(int i=hed[x];i;i=e[i].nxt)
if(vis[e[i].r]==0){
if(e[i].r==L[e[i].num].l) L[e[i].num].c=1;
else L[e[i].num].c=2;
dfs2(e[i].r);
}
}
int main(){
n=Read();m=Read();cnt=0;
for(int i=1;i<=m;i++){
L[i].l=Read();L[i].r=Read();L[i].c=0;
insert(L[i].l,L[i].r,i);
insert(L[i].r,L[i].l,i);
}
dfs1(1);
for(int i=1;i<=n;i++){
if(vis[i]==0){
printf("impossible\n");
return 0;
}
vis[i]=0;hed[i]=0;
}
cnt=0;
for(int i=1;i<=m;i++){
if(L[i].c==0){
insert(L[i].l,L[i].r,i);
insert(L[i].r,L[i].l,i);
}
if(L[i].c==1)
insert(L[i].r,L[i].l,i);
if(L[i].c==2)
insert(L[i].l,L[i].r,i);
}
dfs2(1);
for(int i=1;i<=n;i++)
if(vis[i]==0){
printf("impossible\n");
return 0;
}
for(int i=1;i<=m;i++){
if(L[i].c==2) printf("%d %d\n",L[i].r,L[i].l);
else printf("%d %d\n",L[i].l,L[i].r);
}
return 0;
}

  

  

This passage is made by Iscream-2001.

05-11 21:55