题目概述

有 $n$ 对CP，和 $m$ 对前男女友关系，一对CP（因抢着打隔膜导致电脑爆炸所以）解散之后可能会旧情复燃，导致很多CP都解散。问第 $i$ 对CP解散之后还能否使得所有人都找到新CP。

解题报告

如果第 $i$ 对CP除了直接相连的边之外还能找到另外的增广路，说明就可以CP重组。那么把CP边建成 $(x,y)$ ，而前男女友关系建成 $(y,x)$ ，有多条增广路其实就是有SCC，Tarjan就好了。

ps：不能双向边刷边双，这样可能会把前男女友当成gay佬或者百合与CP搞混。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=8000,maxm=24000;

int n,m,a[maxn+5],b[maxm+5],ans,top,stk[maxn+5],SCC[maxn+5],si[maxn+5];bool instk[maxn+5];
int E,lnk[maxn+5],nxt[maxm+5],son[maxm+5],ti,dfn[maxn+5],low[maxn+5];
struct str {char s[10];} s;int tot;map<str,int> ID;
inline bool operator < (const str &a,const str &b) {return strcmp(a.s,b.s)<0;}

#define reads(x) (scanf("%s",s.s),(x)=ID.count(s)?ID[s]:ID[s]=++tot)
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Tarjan(int x,int pre=0){
    dfn[x]=low[x]=++ti;stk[++top]=x;instk[x]=true;
    for (int j=lnk[x],u;j;j=nxt[j])
        if ((u=son[j])!=pre) if (!dfn[u]) Tarjan(u,x),low[x]=min(low[x],low[u]);
        else if (instk[u]) low[x]=min(low[x],dfn[u]);
    if (dfn[x]==low[x]) for (int y=stk[top--];;y=stk[top--]) {SCC[y]=x;si[x]++;instk[y]=false;if (y==x) break;}
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) reads(a[i]),reads(b[i]),Add(a[i],b[i]);
    scanf("%d",&m);for (int i=1,x,y;i<=m;i++) reads(x),reads(y),Add(y,x);
    for (int i=1;i<=n;puts(si[SCC[a[i++]]]>2?"Unsafe":"Safe")) if (!dfn[a[i]]) Tarjan(a[i]);return 0;
}