题意：
n个点m条无向边（保证图连通）
问：把尽量多的无向边定向，使得最终图保持强连通的特性。
输出：
案例数
最终图的所有单向边 ( 若是不能被定向的无向边则输出u,v && v,u表示2条无向边 )
#
思路：
显然桥是不能被定向的，双连通求出桥。
去掉桥后，对于每个连通分支，可以dfs遍历一遍把经过的边定向，这样一定保证连通分量是强连通的。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#define N 1005
#define M 1000005
using namespace std;
int n,m;//n个点 m条边
struct node
{
int from,to,nex;
int cut;//记录这条边是否为割边
}edge[2*M];//双向边则 edge[i]与edge[i^1]是2条反向边
int head[N] ,edgenum;//在一开始就要 memset(head,-1,sizeof(head)); edgenum=0;
int low[N],dfn[N],tarjin_time;
void add(int u,int v)
{
node E={u,v,head[u],0};
edge[edgenum]=E;
head[u]=edgenum++;
}
void tarjin(int u,int pre)
{
low[u]=dfn[u]= ++tarjin_time;
int flag=1;//flag是阻止双向边的反向边 i和i^1
for(int i=head[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].to;
if(flag&&v==pre)
{
flag=0;
continue;
}
if(!dfn[v])
{
tarjin(v,u);
if(low[u]>low[v])low[u]=low[v];
if(low[v]>dfn[u])//是桥low[v]表示v能走到的最早祖先 有重边且u是v的最早祖先 则low[v]==dfn[u],所以不会当作桥
edge[i].cut=edge[i^1].cut=true;
}
else if(low[u]>dfn[v])low[u]=dfn[v];
}
}
bool liantong;//是否连通
void find_edgecut()
{
memset(dfn,0,sizeof(dfn));
tarjin_time=0;
tarjin(1,1);
liantong=true;
for(int i=1;i<=n;i++)if(!dfn[i]){liantong=false;return;}
}
bool vis[N];
void init(){
for(int i = 0;i<=n;i++)head[i] = -1;
edgenum = 0;
memset(vis, 0, sizeof(vis));
}
void dfs(int u, int fa){
vis[u] = true;
for(int i = head[u]; ~i; i = edge[i].nex){
int v = edge[i].to;
if( edge[i].cut == 1)continue;
if(edge[i^1].cut!=-1)edge[i].cut = -1;
if(!vis[v]) dfs(v, u);
}
}
int main(){
int u, v, Cas = 1;
while(scanf("%d %d",&n,&m), n+m){
init();
while(m--){
scanf("%d %d", &u, &v);
add(u, v);
add(v, u);
}
find_edgecut();
for(int i = 1; i <= n; i++)if(!vis[i])dfs(i, i);
printf("%d\n\n", Cas++);
for(int i = 0; i < edgenum; i++)if(edge[i].cut)printf("%d %d\n", edge[i].from, edge[i].to);
puts("#");
}
return 0;
}