BZOJ 2140 Tarjan
2024-08-31 07:54:16
思路:
跟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=;
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]=;
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]=,p[jy]=T;
}while(jy!=x);
}
}
int main(){
memset(first,-,sizeof(first));
scanf("%d",&n);
for(int i=;i<=n;i++){
cin>>s1>>s2;
mp[s1]=++cnt,mp[s2]=++cnt;
add(cnt,cnt-);
}
scanf("%d",&m);
for(int i=;i<=m;i++){
cin>>s1>>s2;
add(mp[s1],mp[s2]);
}
for(int i=;i<=cnt;i++)if(!dfn[i])tarjan(i);
for(int i=;i<=n;i++){
puts(p[i*]!=p[i*-]?"Safe":"Unsafe");
}
}
最新文章
- 将bean转换成键值列表
- group_concat函数使用
- jquery工具方法parseJSON
- python语法笔记(七)
- Javascript Promise 学习(上)
- android viewpager 深究
- 3、使用Gradle创建Libgdx项目
- Python使用requests库,requests.post格式会引发参数不存在问题
- 家庭记账本之GitHub账号注册与安装(一)
- Mongodb集群搭建之 Sharding+ Replica Sets集群架构(2)
- UVA11525 【Permutation】
- 20165318 2017-2018-2 《Java程序设计》第三周学习总结
- Java并发知识点总结
- day4 数组学习
- css多行文本省略号(...)
- selenium学习网址
- HQL多表查询
- iOS学习笔记(1)--认识Xcode6.1的Interface Builder和常用快捷键
- 学习 SQL 语句 - Select(9): 其他
- windows 系统下git 的使用
热门文章
- asp.net 正则表达式 得到图片url 得到汉字
- SmartUpload实现文件上传
- ANN:ML方法与概率图模型
- 【sqli-labs】 less28a GET- Blind based -All you Union&;Select Belong to us -String -Single quote-parenthesis(GET型基于盲注的去除了Union和Select的单引号带括号字符型注入)
- [系统资源]port range
- [MySQL优化案例]系列 — RAND()优化
- proc程序中使用PLSQL、Exception 、 动态SQL(day08)
- Linux之浅谈VIM常见用法及原理图
- 06.系统编程-4.多线程和GIL
- 【Mail.Ru Cup 2018 Round 2 C】 Lucky Days