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
3 3
1 2
1 3
2 3
输入样例2
4 3
1 2
2 3
3 4
Sample Output
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.