题目：http://codeforces.com/contest/732/problem/F
给无向图定向使得从每个点出发能去的点数最小值最大。
SCC。点内部dfs定向、点间以siz最大的为起点反向dfs。
自我感觉良好的自己写法：在新连边的时候只是操作一下 thd 和 tnxt 即可。
注意写了构造函数的话结构体成员的初值就不是自动赋值为0了。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=4e5+5; int n,m,cnt,col[N],hd[N],xnt=1,thd[N],txnt,siz[N]; int sta[N],top,low[N],dfn[N],tim; bool vis[N],ins[N]; struct Ed{ int tnxt,nxt,fr,to;bool use; Ed(int n=0,int f=0,int t=0):nxt(n),fr(f),to(t) {use=0;}//!!!use=0!!! }ed[N<<1]; void add(int x,int y) { ed[++xnt]=Ed(hd[x],x,y);hd[x]=xnt; ed[++xnt]=Ed(hd[y],y,x);hd[y]=xnt; } void tarjan(int cr,int fa) { dfn[cr]=low[cr]=++tim; sta[++top]=cr;ins[cr]=1; for(int i=hd[cr],v;i;i=ed[i].nxt) if(ins[v=ed[i].to]&&v!=fa)low[cr]=min(low[cr],dfn[v]); else if(!dfn[v])tarjan(v,cr),low[cr]=min(low[cr],low[v]); if(dfn[cr]==low[cr]) { cnt++; while(sta[top]!=cr)col[sta[top]]=cnt,ins[sta[top--]]=0,siz[cnt]++; top--;col[cr]=cnt;ins[cr]=0;siz[cnt]++; } } void dfsx(int cr,int fa) { for(int i=thd[cr];i;i=ed[i].tnxt) { if(col[ed[i].to]!=fa) ed[i^1].use=1,dfsx(col[ed[i].to],cr); } } void dfs(int cr,int fa) { vis[cr]=1; for(int i=hd[cr],v;i;i=ed[i].nxt) { if(col[v=ed[i].to]!=col[cr]||v==fa)continue; if(!ed[i^1].use)ed[i].use=1;//! if(!vis[v])dfs(v,cr);//!vis[v]!! } } int main() { scanf("%d%d",&n,&m);int x,y; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y);add(x,y); } tarjan(1,0); for(int i=2,u,v;i<=xnt;i++) if((u=col[ed[i].fr])!=(v=col[ed[i].to])) ed[i].tnxt=thd[u],thd[u]=i; int mx=0,k; for(int i=1;i<=cnt;i++)if(siz[i]>mx)mx=siz[i],k=i; printf("%d ",mx);dfsx(k,0); for(int i=1;i<=n;i++)if(!vis[i])dfs(i,0); for(int i=2;i<=xnt;i+=2) if(ed[i].use)printf("%d %d ",ed[i].fr,ed[i].to); else printf("%d %d ",ed[i].to,ed[i].fr); return 0; }