Tarjan算法求强连通分量

Tarjan算法求割点和桥

POJ 1236 题目链接

题意

N(2<N<100)各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输，问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。2，至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。

思路

tarjan算法模板题，把整个强连通分量缩成一个点，入度为0的连通分量即可问题1的答案 max(入度为0的个数，出度为0的个数)即为问题2的答案

#include <cstdio> #include <cstring> #include <map> #include <vector> #include <stack> #include <iostream> #include <algorithm> using namespace std; const int N = 111; const int M = 4e4 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; typedef long long ll; struct edge{ int to,nex; }e[N * N]; int head[N],cnt; int dfn[N],low[N]; stack<int> st; int num,ck,clock[N]; bool vis[N]; int cnt1[N],cnt2[N];/// 入度，出度 void add(int u,int v) { e[cnt].to = v; e[cnt].nex = head[u]; head[u] = cnt++; } void dfs(int u) { dfn[u] = low[u] = ++num; vis[u] = true; st.push(u); for (int i = head[u]; i != -1; i = e[i].nex){ int v = e[i].to; if (!dfn[v]){ dfs(v); low[u] = min(low[u],low[v]); } else if (vis[v]){ low[u] = min(low[u],low[v]); } } if (low[u] == dfn[u]){ ck++; while(true){ int x = st.top(); st.pop(); clock[x] = ck; /// 缩点 vis[x] = false; if (x == u) break; } } } void init() { memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(vis,false,sizeof(vis)); memset(low,0,sizeof(low)); memset(cnt1,0,sizeof(cnt1)); memset(cnt2,0,sizeof(cnt2)); while(!st.empty()) st.pop(); num = cnt = ck = 0; } int main() { int n; while(scanf("%d",&n) == 1){ init(); for (int i = 1; i <= n; i++){ int x; while(scanf("%d",&x) && x){ add(i,x); } } for (int i = 1; i <= n; i++){ if (dfn[i] == 0){ dfs(i); } } int ans = 0,res = 0; for (int u = 1; u <= n; u++){ for (int i = head[u]; i != -1; i = e[i].nex){ int v = e[i].to; int x = clock[u],y = clock[v]; if (x != y){ cnt2[x]++; cnt1[y]++; } } } for (int i = 1; i <= ck; i++){ if (!cnt1[i]) ans++; if (!cnt2[i]) res++; } printf("%d\n",ans); printf("%d\n",ck == 1 ? 0 : max(ans,res)); } return 0; }

UVA 315 vj题目链接

题意

给出一张无向图，求割点的个数

思路

tarjan算法求割点模板题 $$要注意的是，不能像求连通分量把第二个min写成low[u]=min(low[u],low[v])$$ $$要写成low[u]=min(low[u],dfn[v])，因为是无向图，所以有可能这个v通过一些边绕到u的父亲结点$$ $$从而使割点数目减少$$

#include <cstdio> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <iostream> #include <algorithm> using namespace std; const int N = 2e4 + 5; const int M = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; typedef long long ll; /** 求割点 一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。 (2) u不为树根，且满足存在(u,v)为树枝边(或称 父子边，即u为v在搜索树中的父亲)，使得 dfn(u)<=low(v)。 （也就是说 V 没办法绕过 u 点到达比 u dfn要小的点） 注：这里所说的树是指，DFS下的搜索树*/ struct edge{ int to,nex; }e[M * 2]; int num,head[N],cnt; int dfn[N],low[N]; set<int> st; void add(int u,int v) { e[cnt].to = v; e[cnt].nex = head[u]; head[u] = cnt++; } void dfs(int u,int fa) { dfn[u] = low[u] = ++num; int son = 0; for (int i = head[u]; i != -1; i = e[i].nex){ int v = e[i].to; if (!dfn[v]){ dfs(v,u); son++; if (fa == -1 && son > 1) st.insert(u); if (fa != -1 && low[v] >= dfn[u]) st.insert(u); low[u] = min(low[u],low[v]); } else if (v != fa){ low[u] = min(low[u],dfn[v]); /// dfn[v] 不能 写成 low[v] } } } void solve(int n) { for (int i = 1; i <= n; i++){ if (!dfn[i]) dfs(i,-1); } cout << st.size() << endl; } void init(int n) { st.clear(); memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); num = cnt = 0; } int main() { int n; while(scanf("%d",&n) == 1 && n){ init(n); int u,v; while(scanf("%d",&u) && u){ char ch; while(scanf("%d%c",&v,&ch)){ add(u,v); add(v,u); if (ch == '\n') break; } } solve(n); } return 0; }

HDU 4612 （重边求桥） 题目链接

题意

n个点，m条边（有重边） 问添加一条新边后，最少的剩下的桥是多少

思路

tarjan缩点，形成一棵树，然后重新建图，把距离最远的两个结点求出来即是可减少的桥数量（可以用两次dfs求出）

#include <cstdio> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <iostream> #include <algorithm> using namespace std; const int N = 2e5 + 5; const int M = 1e6 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; typedef long long ll; struct node{ int to,nex,id; }e[M * 2]; struct node2{ int to,nex; }edge[M * 2]; int num; int low[N],dfn[N]; stack<int> st; bool vis[N]; int block[N],ck; int head[N],cnt; int head2[N],cnt2; vector<vector<int> > g; int mx,mx_id; void addEdge(int u,int v) { edge[cnt2].to = v; edge[cnt2].nex = head2[u]; head2[u] = cnt2++; } void add(int u,int v,int id) { e[cnt].id = id; e[cnt].to = v; e[cnt].nex = head[u]; head[u] = cnt++; } void tarjan(int u,int id) { low[u] = dfn[u] = ++num; vis[u] = true; st.push(u); for (int i = head[u]; i != -1; i = e[i].nex){ int v = e[i].to; if (id == e[i].id) continue; if (!dfn[v]){ tarjan(v,e[i].id); low[u] = min(low[u],low[v]); } else if (vis[v]){ low[u] = min(low[u],dfn[v]); } } if (dfn[u] == low[u]){ ck++; while(true){ int x = st.top(); st.pop(); block[x] = ck; vis[x] = false; if (x == u) break; } } } void dfs(int u,int fa,int d) { if (d > mx){ mx_id = u; mx = d; } for (int i = head2[u]; i != -1; i = edge[i].nex){ int v = edge[i].to; if (v == fa) continue; dfs(v,u,d + 1); } } void solve(int n) { for (int i = 1; i <= n; i++){ if (!dfn[i]) tarjan(i,-1); } for (int u = 1; u <= n; u++){ for (int i = head[u]; i != -1; i = e[i].nex){ int v = e[i].to; int x = block[u],y = block[v]; if (x == y) continue; addEdge(x,y); } } dfs(1,-1,0); dfs(mx_id,-1,0); printf("%d\n",ck - 1 - mx); } void init() { while(!st.empty()) st.pop(); memset(vis,false,sizeof(vis)); memset(head,-1,sizeof(head)); memset(head2,-1,sizeof(head2)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(block,0,sizeof(block)); cnt = cnt2 = ck = num = 0; mx = -1; } int main() { int n,m; while(scanf("%d %d",&n,&m) == 2 && (n || m)){ init(); for (int i = 0; i < m; i++){ int u,v; scanf("%d %d",&u,&v); add(u,v,i); add(v,u,i); } solve(n); } return 0; }

HDU 4635 题目链接

题意

给出了一个有N个节点和M条边的简单有向图。请告诉我你可以添加的最大边数，该图仍然是一个简单的有向图。另外，在添加这些边之后，这个图不能是强连接的。 简单有向图是没有多条边或图循环的有向图。强连通有向图是一种有向图，在有向图中，通过沿边指向的方向遍历边，可以从任何其他节点开始到达任何节点。

思路

最终情况一定是再加一条边，整张图就是强连通的了，那么我们可以把图看成2部分x和y，x和y都是完全图，然后x每个点到y每个点都有边，但是y到x没有边，如果有肯定是强连通了，设x中有a个点，y中有b个点 则 a + b = n 则边数就是 a * (a - 1) + b * (b - 1) + a * b - m，化简得到：n * n - a * b - n - m; 如何让这个值大那就是如何选取x和y的问题了，显然a和b差距越大越好，那么就可以通过tarajan来找出一个包含点最少的强连通分量来当x，其他的强连通分量作为y，这样就很容易了

#include <cstdio> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <iostream> #include <algorithm> using namespace std; const int N = 1e5 + 5; const int M = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; typedef long long ll; struct node{ int to,nex; }e[M * 2]; int num[N],ord; int low[N],dfn[N]; stack<int> st; bool vis[N]; int block[N],ck; int head[N],cnt; int in[N],out[N]; /// 入度，出度 void add(int u,int v) { e[cnt].to = v; e[cnt].nex = head[u]; head[u] = cnt++; } void tarjan(int u) { low[u] = dfn[u] = ++ord; vis[u] = true; st.push(u); for (int i = head[u]; i != -1; i = e[i].nex){ int v = e[i].to; if (!dfn[v]){ tarjan(v); low[u] = min(low[u],low[v]); } else if (vis[v]){ low[u] = min(low[u],dfn[v]); } } if (dfn[u] == low[u]){ ck++; while(true){ int x = st.top(); st.pop(); block[x] = ck; num[ck]++; vis[x] = false; if (x == u) break; } } } void solve(int n,int m) { for (int i = 1; i <= n; i++){ if (!dfn[i]) tarjan(i); } if (ck == 1){ printf("-1\n"); return ; } for (int u = 1; u <= n; u++){ for (int i = head[u]; i != -1; i = e[i].nex){ int v = e[i].to; if (block[u] == block[v]) continue; in[block[u]]++; out[block[v]]++; } } ll ans = 0; ll sum = n * 1ll * n - n - m; for (int i = 1; i <= ck; i++){ if (in[i] == 0 || out[i] == 0){ ans = max(ans,(sum - (n - num[i]) * 1ll * num[i])); } } printf("%I64d\n",ans); } void init() { while(!st.empty()) st.pop(); memset(vis,false,sizeof(vis)); memset(head,-1,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(block,0,sizeof(block)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(num,0,sizeof(num)); cnt = ck = ord = 0; } int main() { int t,Case = 1; scanf("%d",&t); while(t--){ init(); int n,m; scanf("%d %d",&n,&m); for (int i = 0; i < m; i++){ int u,v; scanf("%d %d",&u,&v); add(u,v); } printf("Case %d: ",Case++); solve(n,m); } return 0; }

HDU 4685（强化版poj 1904） 题目链接

题意

n个王子和m个公主，王子只能和他喜欢的公主结婚，公主可以和所有的王子结婚，输出所有王子可能的结婚对象， 必须保证王子与任意这些对象中的一个结婚，都不会影响到剩余的王子的配对数，也就是不能让剩余的王子中突然有一个人没婚可结了。

思路

在poj 1904中

首先建图，如果王子u喜欢妹子v，则建一条边u指向v(u,v)，对于大臣给出的初始完美匹配，如果王子u和妹子v结婚，则建一条边v指向u(v,u)，然后求强连通分量， 对于每个王子和妹子，如果他们都在同一个强连通分量内，则他们可以结婚。 为什么呢？因为每个王子只能和喜欢的妹子结婚，初始完美匹配中的丈夫和妻子之间有两条方向不同的边可以互达，则同一个强连通分量中的王子数和妹子数一定是相等的，若王子x可以和另外的一个妹子a结婚，妹子a的原配王子y肯定能找到另外一个妹子b结婚，因为如果找不到的话，则x和a必不在同一个强连通分量中。 所以一个王子可以和所有与他同一强连通分量的妹子结婚，而这不会导致同一强连通分量中的其他王子找不到妹子结婚。

所以这道题和poj1904唯一的不同就是如果求出完美匹配：

首先做一次最大匹配，设为cnt，那么对于左边，有n-cnt个王子没有匹配，对于右边，有m-cnt个公主没有匹配，所以我们在左边加上m-cnt个虚拟点，这些点喜欢所有公主，右边加上n-cnt个虚拟点，这些点被所有王子喜欢，这样左右两边都是n+m-cnt个点，在求一次最大匹配，这一定是一个完备匹配，对于每一个王子，用他目前匹配的公主，向所有他喜欢的公主连一条有向边，这表示单方面可以替换，所以再对得到的新图求强连通，处在一个强连通分量的公主可以相互替换

#include <cstdio> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <iostream> #include <algorithm> using namespace std; const int N = 2222; const int M = 2e6 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; typedef long long ll; struct node{ int to,nex; }e[M]; int head[N],cnt; int ord; int low[N],dfn[N]; stack<int> st; bool vis[N]; bool g[N][N]; int link[N],link2[N]; int n,m,num_n,num_m; int block[N],ck; vector<int> ans; void add(int u,int v) { e[cnt].nex = head[u]; e[cnt].to = v; head[u] = cnt++; } void tarjan(int u) { low[u] = dfn[u] = ++ord; vis[u] = true; st.push(u); for (int i = head[u]; i != -1; i = e[i].nex){ int v = e[i].to; if (!dfn[v]){ tarjan(v); low[u] = min(low[u],low[v]); } else if (vis[v]){ low[u] = min(low[u],dfn[v]); } } if (dfn[u] == low[u]){ ck++; while(true){ int x = st.top(); st.pop(); block[x] = ck; vis[x] = false; if (x == u) break; } } } bool dfs(int x) { for (int i = 1; i <= num_m; i++){ if (!g[x][i]) continue; if (vis[i]) continue; vis[i] = true; if (!link[i] || dfs(link[i])){ link[i] = x; return true; } } return false; } int match() { int ans = 0; memset(link,0,sizeof(link)); for (int i = 1; i <= num_n; i++){ memset(vis,false,sizeof(vis)); if (dfs(i)) ans++; } return ans; } void solve() { num_n = n; num_m = m; int res = match(); num_n = n + m - res; num_m = num_n; for (int i = 1; i <= num_n; i++){ for (int j = m + 1; j <= num_m; j++){ g[i][j] = true; } } for (int i = n + 1; i <= num_n; i++){ for (int j = 1; j <= num_m; j++){ g[i][j] = true; } } res = match(); for (int i = 1; i <= num_m; i++){ link2[link[i]] = i; } for (int i = 1; i <= num_n; i++){ for (int j = 1; j <= num_m; j++){ if (g[i][j] && link2[i] != j){ add(link2[i],j); } } } memset(vis,false,sizeof(vis)); for (int i = 1; i <= num_m; i++){ if (!dfn[i]) tarjan(i); } for (int i = 1; i <= n; i++){ ans.clear(); for (int j = 1; j <= m; j++){ if (g[i][j] && block[j] == block[link2[i]]){ ans.push_back(j); } } printf("%d",ans.size()); for (auto k : ans){ printf(" %d",k); } printf("\n"); } } void init() { while(!st.empty()) st.pop(); memset(head,-1,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(block,0,sizeof(block)); memset(link2,0,sizeof(link2)); memset(g,false,sizeof(g)); cnt = ck = ord = 0; } int main() { int t,Case = 1; scanf("%d",&t); while(t--){ init(); scanf("%d %d",&n,&m); for (int i = 1; i <= n; i++){ int k; scanf("%d",&k); for (int j = 0; j < k; j++){ int x; scanf("%d",&x); g[i][x] = true; } } printf("Case #%d:\n",Case++); solve(); } return 0; }

HDU 4738 （重边判桥的第二种方法） 题目链接

题意

有n个点，m条边（重边），每条边都有一个权值，问摧毁一个桥所需要的最少权值是多少

思路

重边的第二种处理方法，直接通过堆栈和low[v] > dfn[u]进行判断 如果图不连通，那么不需要派人去 如果有一条桥，权值为0，那么答案应该是1

#include <cstdio> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <iostream> #include <algorithm> using namespace std; const int N = 2e5 + 5; const int M = 1e6 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; typedef long long ll; struct node{ int to,nex,id,len; }e[M * 2]; int ord; int low[N],dfn[N]; stack<int> st; bool vis[N]; int head[N],cnt; vector<int> ans; void add(int u,int v,int id,int len) { e[cnt].id = id; e[cnt].to = v; e[cnt].len = len; e[cnt].nex = head[u]; head[u] = cnt++; } void tarjan(int u,int id) { low[u] = dfn[u] = ++ord; vis[u] = true; st.push(u); for (int i = head[u]; i != -1; i = e[i].nex){ int v = e[i].to; if (id == e[i].id) continue; if (!dfn[v]){ tarjan(v,e[i].id); if (low[v] > dfn[u]){ /// 第二个min没有问题，那这里就能这样写 ans.push_back(e[i].len); } low[u] = min(low[u],low[v]); } else if (vis[v]){ /// 因为有重边，所以必须要在堆栈中才能更新 low[u] = min(low[u],dfn[v]); } } if (dfn[u] == low[u]){ while(true){ int x = st.top(); st.pop(); vis[x] = false; if (x == u) break; } } } void solve(int n) { int res = 0; for (int i = 1; i <= n; i++){ if (!dfn[i]) { tarjan(i,-1); res++; } } if (res > 1){ printf("0\n"); return ; } if (ans.size() == 0){ printf("-1\n"); return ; } sort(ans.begin(),ans.end()); printf("%d\n",ans[0] == 0 ? 1 : ans[0]); } void init() { ans.clear(); while(!st.empty()) st.pop(); memset(vis,false,sizeof(vis)); memset(head,-1,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); cnt = ord = 0; } int main() { int n,m; while(scanf("%d %d",&n,&m) == 2 && (n || m)){ init(); for (int i = 0; i < m; i++){ int u,v,w; scanf("%d %d %d",&u,&v,&w); add(u,v,i,w); add(v,u,i,w); } solve(n); } return 0; }