Tarjan算法_缩点 - 好文

我们这一篇是在已经了解Tarjan算法的基础之上开始写的，如果不了解的话，请先看大牛们关于Tarjan算法的博客。

首先我们先看一下一个问题：一个有向图，有n个点以及m条边，我们至少应该添加几条边才能使整个图变成强连通图。或者是一个无向图至少添加几条边变成连通图。

首先我们对于一个有向无环的图（DAG），至少添加几条边才能使它变为强连通图？我们很容易根据有向无环图的性质得到，我们计算
入度为零的点数为a，出度为零的点数为b，那么我们至少需要添加的边数为max(a,b)，如果只有一个点的话，我们不需要添加任何边。

那么我们怎么把一个图转换为DAG呢，因为上面给出的图可能存在环，那么我们就会想到把已经组成全连通的子图转换成一个点来看，那么我们最终的图就不会包含环了。

好了，解决这类问题的思路已经想好了，下面我们来进行求解：

我们使用Tarjan算法求解出强连通分量之后，我们使用一个belong数组将同一个连通分量的点分配相同的数值，存放在belong数组中，然后我们再次遍历一遍点，然后这次操作的是belong数组中对应的数值，只有把不属于同于个连通分量的边添加到新的图中，并且根据这些边来计算每个缩点的入度以及出度。
//不怕别人比你聪明，就怕别人比你聪明还比你努力 #include<iostream> #include<string>
#include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include
<set> #include <map> #include<vector> #define INF 0x3f3f3f3f using namespace
std; const int MAXN = 1000; struct Node { int fr; int v; int next1;
}edge1[MAXN],edge2[MAXN]; //edge1表示还没有缩点之前的图，edge2表示缩点之后的图的连通关系 int head[MAXN];
int dfn[MAXN],low[MAXN]; int vis[MAXN],stact[MAXN]; int belong[MAXN],num[MAXN];
//belong表示每个点属于的缩完之后的哪一个点，num表示每一个缩点里面有多少个点 int cnt,tot,index,now; void add(int
x,int y,Node* edge) { edge[++cnt].next1 = head[x]; edge[cnt].v = y;
edge[cnt].fr = x; head[x] = cnt; } void Tarjan(int x) { low[x] = dfn[x] =
++tot; vis[x] = 1; stact[++index] = x; for(int i = head[x];i != -1; i =
edge1[i].next1) { int v = edge1[i].v; if(!dfn[v]) { Tarjan(v); low[x] =
min(low[x], low[v]); } else if(vis[v]) low[x] = min(low[x], dfn[v]); }
if(low[x] == dfn[x]) { ++now; do { printf("%d ",stact[index]);
vis[stact[index]] = 0; belong[stact[index]] = now; num[now] ++; index --;
}while(x != stact[index+1]); printf("\n"); } return ; } int main() {
memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low)); memset(vis,0,sizeof(vis));
memset(stact,0,sizeof(stact)); memset(belong,0,sizeof(belong));
memset(num,0,sizeof(num)); cnt = 0;tot = 0;index = 0;now = 0; //now最终表示缩点之后点的数目
int n,m; scanf("%d%d",&n,&m); int x,y; for(int i = 1;i <= m ;i ++) {
scanf("%d%d",&x,&y); add(x,y,edge1); } for(int i = 1;i <= n;i ++) if(!dfn[i])
Tarjan(i); int inde[MAXN];//表示每个缩点的入读 int outde[MAXN];//每个缩点的出度
//缩点完成之后，我们就一定没有环的存在 memset(head,-1,sizeof(head)); int u,v; for(int i = 1;i <=
m;i ++) { u = belong[edge1[i].fr]; v = belong[edge1[i].v];
//表示如果这条边不在缩点之内，那么就是用来连接缩点 if(u!=v) { add(u,v,edge2); inde[v] ++; outde[u] ++;
} } int a = 0,b = 0; //分别计算所的缩点中，入度和出度为0的数目 for(int i = 1;i <= now;i ++) {
if(!inde[i]) a++; if(!outde[i]) b++; } if(now == 1) //如果所有的缩点只有一个，则不需要添加新边
printf("0\n"); else printf("%d\n",max(a,b)); }6 8 1 3 1 2 2 4 3 4 3 5 4 6 4 1 5
6
我们的测试数据如上，答案是需要添加一条边。

我们来看一个例题：Poj 2186 <https://vjudge.net/problem/POJ-2186>

我们要想知道有多说少被全部的认为是受欢迎的，我么先要将他们进行完缩点之后，只有其他的点都可以到达的点才是被其它都欢迎的点。
//不怕别人比你聪明，就怕别人比你聪明还比你努力 //因为和上面程序很类似，所以没有写注释.... include<iostream>
#include<string> #include<algorithm> #include<cstdio> #include<cstring>
#include<cmath> #include <set> #include <stack> #include <map> #include<vector>
#define INF 0x3f3f3f3f using namespace std; const int MAXN = 51000; struct Node
{ int fr; int v; int next1; }edge1[MAXN]; int head[MAXN]; int
dfn[MAXN],low[MAXN]; int vis[MAXN],stact[MAXN]; int belong[MAXN],num[MAXN]; int
cnt,tot,index,now; int n,m; void add(int x,int y,Node* edge) {
edge[++cnt].next1 = head[x]; edge[cnt].v = y; edge[cnt].fr = x; head[x] = cnt;
} void Tarjan(int x) { low[x] = dfn[x] = ++tot; vis[x] = 1; stact[++index] = x;
for(int i = head[x];i != -1; i = edge1[i].next1) { int v = edge1[i].v;
if(!dfn[v]) { Tarjan(v); low[x] = min(low[x], low[v]); } else if(vis[v]) low[x]
= min(low[x], dfn[v]); } if(low[x] == dfn[x]) { ++now; do { vis[stact[index]] =
0; belong[stact[index]] = now; num[now] ++; index --; }while(x !=
stact[index+1]); } return ; } void Init() { memset(head,-1,sizeof(head));
memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low));
memset(vis,0,sizeof(vis)); memset(stact,0,sizeof(stact));
memset(belong,0,sizeof(belong)); memset(num,0,sizeof(num)); cnt = 0;tot =
0;index = 0;now = 0; scanf("%d%d",&n,&m); int x,y; for(int i = 1;i <= m ;i ++)
{ scanf("%d%d",&x,&y); add(x,y,edge1); } } int main() { Init(); for(int i = 1;i
<= n;i ++) if(!dfn[i]) Tarjan(i); int u,v; int outde[MAXN] = {0}; for(int i =
1;i <= m;i++) { u = belong[edge1[i].fr]; v = belong[edge1[i].v]; if(u != v) {
outde[u]++; } } int ans = 0; for(int i =1;i <= now;i ++) { if(!outde[i]) {
if(ans > 0) { printf("0\n"); return 0; } ans = num[i]; } } printf("%d\n",ans);
return 0; }

热门工具换一换