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