稳定婚姻
我也不知道是怎么乱搞出来的……
首先考虑如果拆掉关系之后会怎么样，显然男的会找女的，然后拆散一对夫妻之后男二又去找女二……
由此，形成一个环状的结构，且单向由男连向女。
然后最初的夫妻关系，由女连男，这对应了夫妻的拆开。
接着显然拆掉这条边不会影响其他连通块，以至于只用考虑本连通块
最后意思即为拆开之后这两个点连通(男到女)，就说明找到配对了
也即婚姻不安全的充要条件是这对夫妻在同一个SCC里
绚丽的天空
水题
SCC缩点，然后以入度为零的节点为起点，跑Spfa更新即可
Grass Cownoisseur
先缩点，问题变为找到一条边 \((u,v)\)，使得 \(dis_u+dis’_v\) 最大，其中 \(dis_x\) 表示由 1 到该点的最长路，\(dis'_x\) 表示 \(x\) 到 1的最长路，限制条件是这两个点都可达 1
做法显然，正反图跑一遍Spfa即可
Tourist Reform
显然这个题在边制定方向之后，进行缩点，\(R_i\) 就是出度为 0 的SCC的 siz 的最小值
接着，根据SCC的性质和题目的无向图，不难想到探究SCC和E-DCC的关系，容易发现SCC 把边变成无向之后就变成了E-DCC，那么反之E-DCC也许也可以进行指定方向使得变为SCC
手玩一会可以发现一个E-DCC随便选出一个点开始DFS，搜索树边设为父亲到儿子，返祖边设为儿子到祖先，就可以变成一个SCC，证明显然(形成环)
那么先将这个图缩E-DCC，那么由于图连通，变成了一颗无根树
容易证明无根树树边随便指定方向至少有一个点出度为0（否则边至少 n 条）
由于出度为0是叶子节点，也许并不唯一，考虑将图反过来，变成入度为0，这个点是惟一的，然后将树边反过来即可。
我们可以选择一个点入度为 0，使得 \(R_i\) 等于其 siz，显然应该选择 siz 最大的为根节点，然后将树边全部变为儿子到父亲
各个连通分量直接搜索设边即可
void dfs(int u,int fa){
low[u]=dfn[u]=++num;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v==fa)continue;
if(!dfn[v]){
dfs(v,u);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]){
vis[i]=vis[i^1]=1;
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void dfs2(int u){
c[u]=dcc;siz[dcc]++;
for(int i=head[u];i;i=nxt[i]){
if(vis[i])continue;
int v=ver[i];
if(c[v])continue;
dfs2(v);
}
}
void solve(int u){
for(int i=head[u];i;i=nxt[i]){
if(ans[i/2])continue;
if(vis[i])ans[i/2]=i^1;
else ans[i/2]=i;
int v=ver[i];
if(dis[v])continue;
dis[v]=1;
solve(v);
}
}
void init(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
add(u,v);add(v,u);
}
dfs(1,0);
for(int i=1;i<=n;i++)if(!c[i]){
++dcc;dfs2(i);
}
int mx=0,id=-1;
for(int i=1;i<=dcc;i++)if(mx<siz[i]){
mx=siz[i];id=i;
}
cout<<mx<<"\n";
for(int i=1;i<=n;i++)if(c[i]==id){
solve(i);break;
}
for(int i=1;i<=m;i++){
int u=ver[ans[i]^1],v=ver[ans[i]];
cout<<u<<" "<<v<<"\n";
}
}