有向图的强连通分量:
SSC:给定一个有向图,若图中任意两个点星x,y,存在x->y,且存在y->x,呢么这个图就是强连通分量图.
tarjan求强连通分量:
时间戳:dfn[i],表示搜索的时候首次搜索到i位置的顺序
追溯值:low[i],i的所以孩子存在一条有向边指向i,连接i
1.当结点首次被访问,x入栈,初始化low[x]=dfn[x]
2.(1)扫描从x出发的所以有向边(x->y),若y没有被访问,则(x,y)是树枝边,递归访问y,从y回溯后,令low[x]=min(low[x],low[y])
(2)若y被访问,且y在栈中,则令low[x]=min(low[x],dfn[y]).
3.遍历完从x出发的所以有向边后,如果low[x]==dfn[x],栈中所以元素都是同一连通分量
代码:
#include<bits/stdc++.h> #define MAXN 200005 using namespace std; int to[MAXN<<1],nxt[MAXN<<1],head[MAXN<<1]; int tot,cnt; int low[MAXN],dfn[MAXN],vis[MAXN]; stack<int> st; int stck[MAXN<<1],top; int c[MAXN],num;//c:记录强连通分量,num:强连通分量的数目 void init() { tot=1; top=num=cnt=0; memset(head,0,sizeof(head)); } void add(int u,int v) { to[++tot]=v; nxt[tot]=head[u]; head[u]=tot; } void tarjan(int x) { dfn[x]=low[x]=++cnt; vis[x]=1; st.push(x); for(int i=head[x];i;i=nxt[i]) { int v=to[i]; if(dfn[v]==0) { tarjan(v); low[x]=min(low[x],low[v]); } else{ if(vis[v]!=0){ low[x]=min(low[x],dfn[v]); } } } if(dfn[x]==low[x]) { int k; ++num; do{ k=st.top();st.pop(); vis[k]=0; c[k]=num; }while(x!=k); } } int main() { init(); int n,m,u,v; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d",&u,&v),add(u,v); for(int i=1;i<=n;i++) { if(dfn[i]==0) tarjan(i); } for(int i=1;i<=n;i++) printf("%d %d\n",i,c[i]); return 0; }2.缩点
根据题目,将同一连通分量缩为1个点,然后在新图上处理问题
