SCC统计
2024-09-05 16:06:43
Kosoraju
SCC总数及记录SCC所需要的最少边情况
#include<cstdio>
const int N = ;
int scc_cnt = ;
int Case, n, m, i, x, y, cnt, use[N], g[][N], nxt[][N], v[][N], ed, q[N], t, vis[N], e[N][];
inline void add(int x, int y)
{
v[][++ed] = y;
nxt[][ed] = g[][x];
g[][x] = ed;
v[][ed] = x;
nxt[][ed] = g[][y];
g[][y] = ed;
}
void dfs1(int x)
{
vis[x] = ;
for (int i = g[][x]; i; i = nxt[][i])
if (!vis[v[][i]])
{
use[i] = , dfs1(v[][i]);
}
q[++t] = x;
}
void dfs2(int x)
{
vis[x] = ;
for (int i = g[][x]; i; i = nxt[][i])
if (vis[v[][i]])
{
use[i] = , dfs2(v[][i]);
}
}
int main()
{
scanf("%d", &Case);
while (Case--)
{
scc_cnt = ;
scanf("%d%d", &n, &m);
for (ed = , i = ; i <= n; i++)
{
vis[i] = g[][i] = g[][i] = ;
}
for (i = ; i <= m; i++)
{
scanf("%d%d", &x, &y);
e[i][] = x, e[i][] = y;
add(x, y);
use[i] = ;
}
for (t = , i = ; i <= n; i++)
if (!vis[i])
{
dfs1(i);
}
for (i = n; i; i--)
if (vis[q[i]])
{
scc_cnt++;
dfs2(q[i]);
}
printf("%d\n",scc_cnt);
// cnt = n * 2;
// for (i = 1; i <= m; i++)if (use[i])
// {
// cnt--;
// }
// for (i = 1; i <= m; i++)if (!use[i] && cnt > 0)
// {
// use[i] = 1, cnt--;
// }
// for (i = 1; i <= m; i++)if (!use[i])
// {
// printf("%d %d\n", e[i][0], e[i][1]);
// }
}
}
Tarjan
转自：
https://www.cnblogs.com/stxy-ferryman/p/7779347.html
https://blog.csdn.net/sentimental_dog/article/details/53790582
用处：
1.有向图强连通分量 (一个有向图是强连通的当且仅当G中有一个回路，它至少包含每个节点一次)
2.无向图双连通分量(割点,桥)
3.离线LCA
割顶：若去掉一个点和与这个点相连的边后，图不再连通，则这个点是割顶。
求法：若节点uu存在一棵子树vv满足vv中所有节点的回边都指向uu及以下的节点（即low[v]≥pre[u]low[v]≥pre[u]），则uu是割顶；所以一次DFS即可求出所有割顶。但注意一个特殊情况！根节点是割顶当且仅当它的子节点数严格大于1。
桥：去掉这条边，图不再连通。
求法：若节点uu存在一棵子树vv满足vv中所有节点的回边都指向uu以下（不含uu）的节点（即low[v]>pre[u]low[v]>pre[u]），则边(u,v)(u,v)是桥；所以一次DFS即可求出所有桥。
BCC（点-双连通分量）：连通分量中任意两点间都至少有两条“点不重复路径”。
求法：点双等价于不含割顶的极大子图。但一个问题是割顶本身可能属于多个点双。解决方法是把边分开，即保存一个边的栈。
eBCC（边-双连通分量）：连通分量中任意两点间都至少有两条“边不重复路径”。
求法：边双等价于不含桥的极大子图。一条点不可能分属多个边双（否则可以将这些个边双合并）。所以一次DFS求出所有桥，再来一次DFS把边双分开即可（DFS到桥就不走）。
前向星版SCC
void tarjan(int x)
{
dfn[x] = ++deep;
low[x] = deep;
visit[x] = ;
sta[++top] = x;
for (int i = Head[x]; i; i = nxt[i])
{
int v = to[i];
if (!dfn[v])
{
tarjan(v);
low[x] = min(low[x], low[v]);
}
else
{
if (visit[v])
{
low[x] = min(low[x], low[v]);
}
}
}
if (dfn[x] == low[x])
{
color[x] = ++colorsum;
visit[x] = ;
while (sta[top] != x)
{
color[sta[top]] = colorsum;
visit[sta[top--]] = ;
}
top--;
}
}
[USACO06JAN]The Cow Prom
算强连通分量中点数不小于1的个数
/*#include<cstring>#include<algorithm>#include<queue>#include<vector>#include<cstdio>#include<cmath>#include<iostream>*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
vector<int> gra[maxn];
int dfn[maxn];//表示这个点在dfs的时候是第几个搜到的；
int low[maxn];//表示这个点及其子节点连的所有点里dfn的最小值
int sta[maxn];//存着当前所有可能能构成强连通分量的点
int visit[maxn];//表示一个点目前是否在sta中
int cnt[maxn];//各个强连通分量中含点的数目
int color[maxn];//表示一个点属于哪个强连通分量
int deep;/*表示从前有多少个点被搜到*/
int top;/*sta目前的大小*/
int colorsum = ;/*目前强连通分量的数目*/
int ans = ;
int n, m;
void tarjan(int x)
{
dfn[x] = ++deep;
low[x] = deep;
visit[x] = ;
sta[++top] = x;
int sz = gra[x].size();
for (int i = ; i < sz; i++)
{
int to = gra[x][i];
if (!dfn[to])
{
tarjan(to);
low[x] = min(low[x], low[to]);
}
else
{
if (visit[to])
{
low[x] = min(low[x], low[to]);
}
}
}
if (dfn[x] == low[x])
{
color[x] = ++colorsum;
visit[x] = ;
while (sta[top] != x)
{
color[sta[top]] = colorsum;
visit[sta[top--]] = ;
}
top--;
}
}
int main()
{
cin >> n >> m;
int from, to;
for (int i = ; i <= m; i++)
{
cin >> from >> to;
gra[from].push_back(to);
}
for (int i = ; i <= n; i++)
{
if (!dfn[i])
{
tarjan(i);
}
}
for (int i = ; i <= n; i++)
{
cnt[color[i]]++;
}
for (int i = ; i <= colorsum; i++)
{
if (cnt[i] > )
{
ans++;
}
}
cout << ans << endl;
}
poj2186 Popular Cows
缩点后求出度为0的点的个数(如果求得的点为缩点后的超级点需要特判)
/*#include<cstring>#include<algorithm>#include<queue>#include<vector>#include<cstdio>#include<cmath>#include<iostream>*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
vector<int> gra[maxn];
int du[maxn];
int dfn[maxn];//表示这个点在dfs的时候是第几个搜到的；
int low[maxn];//表示这个点及其子节点连的所有点里dfn的最小值
int sta[maxn];//存着当前所有可能能构成强连通分量的点
int visit[maxn];//表示一个点目前是否在sta中
int cnt[maxn];//各个强连通分量中含点的数目
int color[maxn];//表示一个点属于哪个强连通分量
int deep;/*表示从前有多少个点被搜到*/
int top;/*sta目前的大小*/
int colorsum = ;/*目前强连通分量的数目*/
int ans = ;
int n, m;
void tarjan(int x)
{
dfn[x] = ++deep;
low[x] = deep;
visit[x] = ;
sta[++top] = x;
int sz = gra[x].size();
for (int i = ; i < sz; i++)
{
int to = gra[x][i];
if (!dfn[to])
{
tarjan(to);
low[x] = min(low[x], low[to]);
}
else
{
if (visit[to])
{
low[x] = min(low[x], low[to]);
}
}
}
if (dfn[x] == low[x])
{
color[x] = ++colorsum;
visit[x] = ;
while (sta[top] != x)
{
color[sta[top]] = colorsum;
visit[sta[top--]] = ;
}
top--;
}
}
int main()
{
int temp = ;
cin >> n >> m;
int from, to;
for (int i = ; i <= m; i++)
{
cin >> from >> to;
gra[from].push_back(to);
}
for (int i = ; i <= n; i++)
{
if (!dfn[i])
{
tarjan(i);
}
}
for (int i = ; i <= n; i++)
{
int len = gra[i].size();
for (int j = ; j < len; j++)
{
int to = gra[i][j];
if (color[to] != color[i]) //如果缩点后两个点不在一个强连通分量内
{
du[color[i]]++;
}
}
cnt[color[i]]++;
}
for (int i = ; i <= colorsum; i++)
{
if (temp > )
{
cout << << endl;
return ;
}
if (du[i] == )
{
temp++;
ans = cnt[i];
}
}
cout << ans << endl;
}
洛谷3388 求割点并输出模板题（附带桥输出）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
vector<int> gra[maxn];
int dfn[maxn];//表示这个点在dfs的时候是第几个搜到的；
int low[maxn];//表示这个点及其子节点连的所有点里dfn的最小值
int iscut[maxn];//表示这个点是否是割点
int deep;/*表示从前有多少个点被搜到*/
int ans = ;
int n, m;
int tarjan(int x, int pre)
{
int child = ;
int lowx;
lowx = dfn[x] = ++deep;
int len = gra[x].size();
for (int i = ; i < len; i++)
{
int to = gra[x][i];
if (!dfn[to])
{
child++;
int lowto = tarjan(to, x);
lowx = min(lowx, lowto);
if (lowto >= dfn[x])
{
iscut[x] = ;
}
// if (lowto > dfn[x])
// {
// cout << "bridge " << x << " " << to << endl;
// }
}
else
{
if (to != pre && dfn[to] < dfn[x])
{
lowx = min(lowx, dfn[to]);
}
}
}
if (pre < && child == )
{
iscut[x] = ;
}
low[x] = lowx;
return lowx;
}
int main()
{
int temp = ;
cin >> n >> m;
int from, to;
for (int i = ; i <= m; i++)
{
cin >> from >> to;
gra[from].push_back(to);
gra[to].push_back(from);
}
for (int i = ; i <= n; i++)
{
if (!dfn[i])
{
tarjan(i, -);
}
}
for (int i = ; i <= n; i++)
{
if (iscut[i])
{
ans++;
}
}
cout << ans << endl;
for (int i = ; i <= n; i++)
{
if (iscut[i])
{
cout << i << " ";
}
}
cout << endl;
}
Codeforces 962 F
求点双连通分量中的边
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + ;
const int gakki = + + + + 1e9;
const int MAXN = 2e5 + ;
const int MAXM = 2e5 + ;
int to[MAXM << ], nxt[MAXM << ], Head[MAXN], tot = ;
inline void addedge(int u, int v)
{
to[++tot] = v;
nxt[tot] = Head[u];
Head[u] = tot;
}
int n, m;
int dfn[MAXN], low[MAXN], dfs_clock = ;
int BCCcnt = , blong[MAXN], inque[MAXM << ];
int st[MAXN], l = , ans[MAXN], ansnum = ;
bool vis[MAXM << ];
void tarjanBCC(int x, int fa)
{
dfn[x] = low[x] = ++dfs_clock;
for (int i = Head[x]; i; i = nxt[i])
{
int v = to[i];
if (v == fa || vis[i])
{
continue;
}
vis[i] = vis[i ^ ] = ;
st[l++] = i;
if (!dfn[v])
{
tarjanBCC(v, x);
low[x] = min(low[v], low[x]);
if (dfn[x] <= low[v])
{
int now, vnumber = , enumber = ;
BCCcnt++;
while()
{
now = st[--l];
if (blong[to[now]] != BCCcnt)
{
blong[to[now]] = BCCcnt, ++vnumber;
}
if (blong[to[now ^ ]] != BCCcnt)
{
blong[to[now ^ ]] = BCCcnt, ++vnumber;
}
inque[++enumber] = now;
if(now==i)
break;
}
if (vnumber == enumber)
{
for (int i = ; i <= enumber; i++)
{
ans[++ansnum] = inque[i] / ;
}
}
}
}
else
{
low[x] = min(low[x], dfn[v]);
}
}
}
int main()
{
ios_base::sync_with_stdio();
cin.tie();
cin >> n >> m;
int u, v;
for (int i = ; i <= m; i++)
{
cin >> u >> v;
addedge(u, v), addedge(v, u);
}
for (int i = ; i <= n; i++)
{
if (!dfn[i])
{
tarjanBCC(i, -);
}
}
sort(ans + , ans + + ansnum);
cout << ansnum << endl;
for (int i = ; i <= ansnum; i++)
{
cout << ans[i] << " ";
}
return ;
}
附:求边双连通分量中的边
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+;
int dfn[N],low[N],H[N],nxt[N<<],to[N<<];
int n,m,x,y,cnt,tot=;
bool ib[N],is[N];
void add(int x,int y){
to[++tot]=y;nxt[tot]=H[x];H[x]=tot;
}
void dfs(int u,int fa){
low[u]=dfn[u]=++cnt;
int chi=;
for(int i=H[u];i;i=nxt[i]){
int v=to[i];
if(v==fa) continue;
if(!dfn[v]) {
++chi;
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]) ib[i]=ib[i^]=;
if(low[v]>=dfn[u]) is[u]=;
}
else low[u]=min(low[u],dfn[v]);
}
if(chi==&&fa==-) is[u]=;
}
int num,bnum,a[N],A[N],ans;
void dfs2(int u,int fa){
++num;for(int i=H[u];i;i=nxt[i]) {
int v=to[i];
if(ib[i]||ib[i^]||v==fa) continue;
ib[i]=ib[i^]=;
a[++bnum]=i>>;
if(!dfn[v]) dfn[v]=,dfs2(v,u);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;++i) {
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=;i<=n;++i) if(!dfn[i]) dfs(i,-);
for(int i=;i<=n;++i) dfn[i]=;
for(int i=;i<=n;++i) if(!dfn[i]) {
num=bnum=;
dfn[i]=;
dfs2(i,-);
if(num==bnum) for(int j=;j<=num;++j) A[++ans]=a[j];
}
printf("%d\n",ans);
sort(A+,A+ans+);
for(int i=;i<=ans;++i) printf("%d ",A[i]);
}
最新文章
- 将字符串中的URL 解析，获取内容
- avi文件打开出现花屏、打开不了问题
- JSP计算器
- sql 查询效率
- 配置Hadoop开发环境（Eclipse）
- Hadoop虽然强大，但不是万能的(CSDN)
- IOS 封装类的时候注释格式,使用的时候可以想官方库一样快捷显示
- SSIS 学习（2）：数据流任务（上）【转】
- linux中curl命令
- Android Intent传递数据
- spring AOP 是如何一步一步被简化的
- net Mvc模块化开发
- CSS格式与布局中三种位置的理解与应用
- c++ 回调函数使用
- 想进大厂，想收获高薪offer，资深猎头告诉你怎么做......
- C++ 使用命名规范
- vue-router路由管理器
- vbs学习笔记2——创建桌面快捷方式
- 【转】RTMP/RTP/RTSP/RTCP协议对比与区别介绍
- 我所知道的MVVM框架(转 司徒大大 )