思路:
跟POJ有一道时限挺长的题一模一样 哦 POJ 1904
题解可以看这个(捂脸)
http://blog.csdn.net/qq_31785871/article/details/52963278
//By SiriusRen
#include <map>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=55555;
int n,m,v[N],next[N],tot,first[N],stk[N],top,jy,p[N],cnt,T,Cnt,dfn[N],low[N],vis[N];
string s1,s2;
map<string,int>mp;
void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}
void tarjan(int x){
dfn[x]=low[x]=++Cnt,stk[++top]=x,vis[x]=1;
for(int i=first[x];~i;i=next[i]){
if(!dfn[v[i]])tarjan(v[i]),low[x]=min(low[x],low[v[i]]);
else if(vis[v[i]])low[x]=min(low[x],dfn[v[i]]);
}
if(low[x]==dfn[x]){
T++;
do{
jy=stk[top--],vis[jy]=0,p[jy]=T;
}while(jy!=x);
}
}
int main(){
memset(first,-1,sizeof(first));
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>s1>>s2;
mp[s1]=++cnt,mp[s2]=++cnt;
add(cnt,cnt-1);
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
cin>>s1>>s2;
add(mp[s1],mp[s2]);
}
for(int i=1;i<=cnt;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++){
puts(p[i*2]!=p[i*2-1]?"Safe":"Unsafe");
}
}
转载于:https://www.cnblogs.com/SiriusRen/p/6592611.html