做a动漫视频在线观看网站,潍坊住房和城乡建设局招标网站,网站开发结构有,WordPress关站插件传送门 这道题一开始可能以为是二分图匹配……#xff1f;不过后来发现和二分图没啥大关系。 简单分析之后发现#xff0c;把夫妻之间连边#xff08;男性向女性连边#xff09;#xff0c;之后再将每对曾经是情侣的人连边#xff08;女性向男性连边#xff09;#xf…传送门 这道题一开始可能以为是二分图匹配……不过后来发现和二分图没啥大关系。 简单分析之后发现把夫妻之间连边男性向女性连边之后再将每对曾经是情侣的人连边女性向男性连边当然以上的方向可以反过来不过两次连接方向必须相反。这样的话如果婚姻是危险的那么这些就是在一个强连通分量里面的。换句话说如果一个强连通分量中有多于1个点那么就说明这个婚姻并不稳定夫妻之间连单向边所以如果婚姻稳定的话夫妻不会出现在一个强连通分量之中 这样的话就比较好办了直接如上述方法见图之后跑tarjan求出强连通分量记录下来每个强连通分量之中的点数即可。还有这道题需要使用map映射一下。 看一下代码。 #includecstdio
#includealgorithm
#includecstring
#includeiostream
#includecmath
#includequeue
#includeset
#includemap
#define rep(i,a,n) for(int i a;i n;i)
#define per(i,n,a) for(int i n;i a;i--)
#define enter putchar(\n)using namespace std;
typedef long long ll;
const int M 50005;int read()
{int ans 0,op 1;char ch getchar();while(ch 0 || ch 9){if(ch -) op -1;ch getchar();}while(ch 0 ch 9){ans * 10;ans ch - 0;ch getchar();}return ans * op;
}struct edge
{int next,to;
}e[M2];
int n,m,cnt,ecnt,cur,low[M],dfn[M],stack[M],top,curr,vis[M],belong[M],head[M];
bool in[M];
string f[M],a,b;
map string,int p;void add(int x,int y)
{e[ecnt].to y;e[ecnt].next head[x];head[x] ecnt;
}void tarjan(int x)
{low[x] dfn[x] cur;in[x] 1,stack[top] x;for(int i head[x];i;i e[i].next){if(!dfn[e[i].to]) tarjan(e[i].to),low[x] min(low[x],low[e[i].to]);else if(in[e[i].to]) low[x] min(low[x],dfn[e[i].to]);}if(dfn[x] low[x]){int p;curr;while(p stack[top--]){in[p] 0,belong[p] curr;if(x p) break;}}
}
void solve()
{rep(i,1,cnt) if(!dfn[i]) tarjan(i);rep(i,1,cnt) vis[belong[i]];for(int i 1;i n1;i 2){if(vis[belong[p[f[i]]]] 1) printf(Unsafe\n);else printf(Safe\n);}
}int main()
{n read();rep(i,1,n){cin a b;f[cnt] a,p[a] cnt;f[cnt] b,p[b] cnt;add(cnt-1,cnt);}m read();rep(i,1,m) cin a b,add(p[b],p[a]);solve();return 0;
} 转载于:https://www.cnblogs.com/captain1/p/9671229.html
