大致题意:
给出一个有向图,现在要删去一个点使得剩下的图中含有点数最多的强连通分量最小。
大致思路:
枚举删点,每次求一遍强连通分量即可
#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=3150;
const int mMax=20100;
class edge{
public:
int v,nex;
};edge e[mMax];
int k,head[nMax];
void addedge(int a,int b){
e[k].v=b;
e[k].nex=head[a];
head[a]=k;k++;
}
int dfn[nMax],low[nMax],sta[nMax],top,atype,belon[nMax],dep,pnum[nMax];
bool insta[nMax];
void Tarjan(int u,int dnum){
int i,j;
dfn[u]=low[u]=++dep;
sta[++top]=u;
insta[u]=1;
for(i=head[u];i;i=e[i].nex){
int v=e[i].v;
if(v==dnum)continue;
if(!dfn[v]){
Tarjan(v,dnum);
low[u]=min(low[u],low[v]);
}
else{
if(insta[v])low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
atype++;
do{
j=sta[top--];
belon[j]=atype;
pnum[atype]++;
insta[j]=0;
}while(u!=j);
}
}
void init(){
// k=1;
dep=1;
top=atype=0;
memset(pnum,0,sizeof(pnum));
memset(insta,0,sizeof(insta)); //?????
// memset(head,0,sizeof(head)); //???????
memset(low,0,sizeof(low)); //Tarjan?low??
memset(dfn,0,sizeof(dfn)); //Tarjan?dfn??
memset(belon,0,sizeof(belon));
}
int main(){
int i,j,m,n,a,b,ans;
while(cin>>n>>m)
{
ans=inf;
k=1;
memset(head,0,sizeof(head));
for(i=0;i<m;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
}
for(int dnum=0;dnum<n;dnum++){
init();
for(i=0;i<n;i++){
if(!dfn[i]&&i!=dnum)Tarjan(i,dnum);
}
int maxx=0;
for(i=1;i<=atype;i++){
maxx=max(pnum[i],maxx);
}
ans=min(maxx,ans);
}
if(ans==1)ans=0;
cout<<ans<<endl;
}
return 0;
}
分享到:
相关推荐
实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...
Tarjan 的算法将一个有向(可能是循环的!)图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不...
LCA Tarjan: 实现原理 理解:离线算法,建好树后再查询,一次DFS 吧所有查询解决完。 时间复杂度:O(n+q); n个点 q次询问 补一下:链式向前星,并查集 ,Tarjan 代码 #include #include #include #include #...
tarjan求割边
Tarjan模板题 补习: AC code: /* Tarjan求有向图的强连通分量, */ #include #include #include #include #include using namespace std; const int MAXN = 1e5 + 10; struct Edge{ int to, next, dis; }edge...
Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法 (本篇文章...
最近公共祖先LCA Tarjan算法
Tarjan 算法论文 DEPTH-FIRST SEARCH AND LINEAR GRAPH ALGORITHMS.pdf
c++写的Tarjan 的 LCA 算法,最近公共祖先算法,可供算法学习参考
更精细的追踪每一个步骤,力求完全剖析算法。
Tarjan 算法是图论中非常实用 / 常用的算法之一,能解决强连通分量,双连通分量,割点和桥,求最近公共祖先(LCA)等问题。 关于 Tarjan 算法,笔者将用一系列文章系统介绍 Tarjan 算法的原理以及其主要解决的问题...
Tarjan应用LCA
Tarjan割点割边,强联通分量讲解
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...
tarjan算法呕心沥血之作,动画演示,步步清晰可见,详细的描述了tarjan算法的工作过程,比网上的单纯的图片更加容易理解。
C++实现Tarjan算法的一个简单模板,求有向图的强连通分量。时间复杂度为O(N+M)。
void Tarjan(int cur); int Map[maxn][maxn]; int n,m; int tol,t; //6 8 //1 3 //1 2 //2 4 //3 4 //3 5 //4 1 //4 6 //5 6 int main() { cin>>n>>m; int x,y; for(int i=0;i;i++){ cin>>x>>y; Map[x][y]=1; ...
Tarjan-Languer快速算法,用于在流程图中查找支配者 原料药 var pipeline = require ( 'tarjan' ) . create ( 'dominance' ) ; // Initialize pipeline // ... // ... var tarjan = require ( 'tarjan' ) . create ...
Tarjan是使用Tarjan算法的图循环检测功能。 该算法获取输入图并生成一个切片,其中每个项目都是一个高度连接的顶点的切片。 输入图采用地图的形式,其中键是图形顶点,值是一个切片的for的边。 算法说明: : ...
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573