Tarjan
Skyzhou666
·
·
算法·理论
Tarjan（链表）
找了半天终于找到一篇用链表的blog（
Tarjan详细讲解
Tarjan缩点后建新图模板
```cpp
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#include <cstdio>
#define MAXN 10001
using namespace std;
int n, m, dfn[MAXN], low[MAXN], cnt, coli, col[MAXN], nums[MAXN];
vector <int> g[MAXN], ng[MAXN];
bool vis[MAXN];
stack <int> st;
void Tarjan(int u)
{
//cout << u << endl;
dfn[u] = low[u] = ++cnt;
st.push(u);
vis[u] = true;
for(int x = 0; x < g[u].size(); x++)
{
int v = g[u][x];
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])
{
coli++;
int v;
do
{
v = st.top(); st.pop();
vis[v] = false;
col[v] = coli;
nums[coli]++;
} while(v != u);
}
}
int main()
{
cin >> n >> m;
for(int x = 0; x < m; x++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
}
for(int x = 1; x <= n; x++)
if(!dfn[x]) Tarjan(x);
for(int x = 1; x <= n; x++)
{
for(int y = 0; y < g[x].size(); y++)
{
int v = g[x][y];
if(col[x] != col[v]) ng[col[x]].push_back(col[v]);
}
}
for(int x = 1; x <= coli; x++)
{
cout << nums[x] << endl;
for(int y = 0; y < ng[x].size(); y++) cout << x << " " << ng[x][y] << " ";
cout << endl;
}
return 0;
}
```
### 这边丢一个P1551亲戚的Tarjan做法
虽然是并查集板子题但用来练Tarjan也是可以的（
```cpp
#include <iostream>
#include <vector>
#define MAXN 100001
using namespace std;
vector <int> g[MAXN];
bool vis[MAXN];
int sta[MAXN], low[MAXN], dfn[MAXN], color[MAXN], coli, sti, cnt;
void Tarjan(int u)
{
dfn[u] = low[u] = ++cnt;
sta[++sti] = u;
vis[u] = true;
for(int x = 0; x < g[u].size(); x++)
{
int v = g[u][x];
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])
{
coli++;
while(sta[sti+1] != u)
{
int v = sta[sti--];
color[v] = coli;
}
}
}
int main()
{
int n, m, p;
cin >> n >> m;
for(int x = 0; x < m; x++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int x = 0; x < n; x++)
if(!dfn[x]) Tarjan(x);
cin >> p;
for(int x = 0; x < p; x++)
{
int u, v;
cin >> u >> v;
if(color[u] == color[v]) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
```
### P2835 刻录光盘（经典例题）
Tarjan缩点，找入度为0的强连通分量（即必须获得资料）
```cpp
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#include <cstdio>
#define MAXN 1001
using namespace std;
int n, dfn[MAXN], low[MAXN], cnt, coli, col[MAXN], in[MAXN];
vector <int> g[MAXN];
bool vis[MAXN];
stack <int> st;
void Tarjan(int u)
{
//cout << u << endl;
dfn[u] = low[u] = ++cnt;
st.push(u);
vis[u] = true;
for(int x = 0; x < g[u].size(); x++)
{
int v = g[u][x];
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])
{
coli++;
int v;
do
{
v = st.top(); st.pop();
vis[v] = false;
col[v] = coli;
} while(v != u);
}
}
int main()
{
cin >> n;
for(int x = 1; x <= n; x++)
{
int v;
cin >> v;
while(v != 0)
{
g[x].push_back(v);
cin >> v;
}
}
for(int x = 1; x <= n; x++)
if(!dfn[x]) Tarjan(x);
int ans = 0;
for(int x = 1; x <= n; x++)
for(int y = 0; y < g[x].size(); y++)
{
int v = g[x][y];
if(col[x] != col[v]) in[col[v]]++;
}
//for(int x = 1; x <= n; x++) cout << in[x] << " ";
//cout << endl;
for(int x = 1; x <= coli; x++)
if(!in[x]) ans++;
cout << ans << endl;
return 0;
}
```
### P8436 边双连通分量模板
**其实就是无向图Tarjan模板**
这里因为数据有重边就给边加了个id记录，反向边id相同就不跑，但重边id不同就继续跑
```cpp
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
#define MAXN 500001
using namespace std;
struct edge
{
int v, id;
};
int dfn[MAXN], low[MAXN], cnt, coli;
bool vis[MAXN];
stack <int> st;
vector <edge> g[MAXN];
vector <int> col[MAXN];
void Tarjan(int u, int lst)
{
dfn[u] = low[u] = ++cnt;
vis[u] = true;
st.push(u);
for(int x = 0; x < g[u].size(); x++)
{
int v = g[u][x].v, id = g[u][x].id;
if(id == lst) continue;
if(!dfn[v])
{
Tarjan(v, id);
low[u] = min(low[u], low[v]);
}
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u])
{
coli++;
int v;
do
{
v = st.top(); st.pop();
vis[v] = false;
col[coli].push_back(v);
} while(v != u);
}
}
int main()
{
int n, m;
cin >> n >> m;
for(int x = 1; x <= m; x++)
{
int u, v;
cin >> u >> v;
g[u].push_back((edge){v, x});
g[v].push_back((edge){u, x});
}
for(int x = 1; x <= n; x++)
if(!dfn[x]) Tarjan(x, 0);
cout << coli << endl;
for(int x = 1; x <= coli; x++)
{
cout << col[x].size() << " ";
for(int y = 0; y < col[x].size(); y++) cout << col[x][y] << " ";
cout << endl;
}
return 0;
}
```