http://poj.org/problem?id=3180

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#include<string>
#include<stack>
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pqueue priority_queue
#define NEW(a,b) memset(a,b,sizeof(a))
#define lowbit(x) ((x)&(-x))
const double pi=4.0*atan(1.0);
const int maxn=1e5+;
typedef long long LL;
typedef unsigned long long ULL;
const LL mod=1e9+;
const ULL base=1e7+;
using namespace std;
struct node{
int to,nxt;
}g[maxn*];
int head[maxn];
int cnt=;
void add(int u,int v){
g[cnt].to=v;
g[cnt].nxt=head[u];
head[u]=cnt++;
}
int deep=;
int dfn[maxn],low[maxn];
bool vis[maxn];
int Stack[maxn];
int tail=;
int ans=;
void tarjan(int u){
dfn[u]=++deep;
low[u]=deep;
Stack[++tail]=u;
vis[u]=;
int t=head[u];
int r=;
while(t!=-){
if(!dfn[g[t].to]){
tarjan(g[t].to);
low[u]=min(low[u],low[g[t].to]);
}
else{
if(vis[g[t].to]){
low[u]=min(low[u],low[g[t].to]);
}
}
t=g[t].nxt;
}
if(dfn[u]==low[u]){
while(Stack[tail]!=u){
vis[Stack[tail]]=;
tail--;
r=;
}
vis[Stack[tail]]=;
tail--;
}
ans+=r;
}
int main(){
memset(head,-,sizeof(head));
int n,m,x,y;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
cout<<ans<<endl;
}

无向图缩点

http://codeforces.com/group/w1oiqifZbS/contest/652/problem/E

#include<bits/stdc++.h>
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pqueue priority_queue
#define NEW(a,b) memset(a,b,sizeof(a))
#define lowbit(x) ((x)&(-x))
const double pi=4.0*atan(1.0);
const int maxn=3e5+;
typedef long long LL;
typedef unsigned long long ULL;
const LL mod=1e9+;
const ULL base=1e7+;
using namespace std;
struct node{
int to,nxt;
bool val;
}g[maxn*],gg[maxn*];
int head[maxn],head2[maxn];
int cnt=;
void add(int u,int v,bool val){
g[cnt].to=v;
g[cnt].nxt=head[u];
g[cnt].val=val;
head[u]=cnt++;
}
int deep=;
int dfn[maxn],low[maxn];
bool vis[maxn];
bool used[maxn];
int Stack[maxn];
bool a[maxn];
int color[maxn];
int tot=;
int tail=;
int n,m;
void tarjan(int u,int fa){
dfn[u]=++deep;
low[u]=deep;
Stack[++tail]=u;
vis[u]=;
int t=head[u];
while(t!=-){
if(g[t].to==fa){
t=g[t].nxt;
continue;
}
if(!dfn[g[t].to]){
tarjan(g[t].to,u);
low[u]=min(low[u],low[g[t].to]);
}
else{
if(vis[g[t].to]){
low[u]=min(low[u],low[g[t].to]);
}
}
t=g[t].nxt;
}
if(dfn[u]==low[u]){
tot++;
while(Stack[tail]!=u){
vis[Stack[tail]]=;
color[Stack[tail]]=tot;
tail--;
}
vis[Stack[tail]]=;
color[Stack[tail]]=tot;
tail--;
}
}
void add2(int u,int v,int val){
gg[cnt].to=v;
gg[cnt].nxt=head2[u];
gg[cnt].val=val;
head2[u]=cnt++;
}
void suodian(){
for(int i=;i<=n;i++){
int t=head[i];
while(t!=-){
if(color[i]==color[g[t].to]){
a[color[i]]+=g[t].val;
}
else if(g[t].to>i){
//cout<<i<<' '<<g[t].to<<endl;
add2(color[i],color[g[t].to],g[t].val);
add2(color[g[t].to],color[i],g[t].val);
}
t=g[t].nxt;
}
}
}
bool ans=;
void dfs2(int u,int fa,int aim,bool re){
//cout<<u<<endl;
if(u==aim){
ans+=re;
return ;
}
int t=head2[u];
while(t!=-){
if(gg[t].to!=fa){
dfs2(gg[t].to,u,aim,re+gg[t].val+a[gg[t].to]);
}
t=gg[t].nxt;
}
}
int main(){
memset(head,-,sizeof(head));
memset(head2,-,sizeof(head2));
int x,y,val;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d%d",&x,&y,&val);
add(x,y,(bool)val);
add(y,x,(bool)val);
}
int s,t;
scanf("%d%d",&s,&t);
for(int i=;i<=n;i++){
if(!dfn[i]){
tarjan(i,);
}
}
cnt=;
suodian();
dfs2(color[s],,color[t],a[color[s]]);
if(ans){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}

最新文章

  1. 纯Swift编写的仿“随遇”应用源码
  2. Javascript 中的严格模式
  3. Page 指令的各个属性及其功能
  4. 微信支付开发-当前页面的URL未注册
  5. 【转】wait,notify,notifyAll,join,yield,sleep的区别和联系
  6. 【tornado】系列项目(一)之基于领域驱动模型架构设计的京东用户管理后台
  7. try catch finally的一些用法
  8. Extjs 控件属性(部分)
  9. SSH2 架构常用注解
  10. linux硬件驱动层
  11. ionic安装拍照选照片插件
  12. IIS Hang Troubleshoot
  13. vector中resize和reserve的区别,代码验证
  14. xcode 没有 iphone4s 模拟器 的解决方法..
  15. Vue 项目: npm run dev 报错 webpack-dev-server
  16. adoop(四)HDFS集群详解
  17. LOJ558 我们的 CPU 遭到攻击 LCT
  18. [转]Visual Studio 2010 中安装Qt 5.1
  19. 使用svn导入项目
  20. Path-O-LOGIC Keynote

热门文章

  1. 【如皋OJ】1127:正整数N转换成一个二进制数
  2. mat函数
  3. LeetCode——17. Letter Combinations of a Phone Number
  4. Scrapy实战篇(六)之爬取360图片数据和图片
  5. CentOS 7下Samba服务安装与配置详解
  6. goland scope pattern 设置
  7. Spark-RPC理解
  8. [STM32F103]定时器PWM输入
  9. 接口与继承:方法覆盖(super)
  10. 【HDFS API编程】jUnit封装-改写创建文件夹