Tarjan算法求连通分量 割点 LCA模版

连通分量(low相同即为连通分量)

#include 
#include 
#include 
#include 
using namespace std;
int dfn[100],low[100];
int e[100],h[100],ne[100];
int idx,times,vi[100];
vector color[100];
vector s;
void add(int a,int b)
{
    e[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
}
void dfs(int x)
{
    s.push_back(x);
    vi[x]=true;
    dfn[x]=low[x]=++times;//记录时间戳
    for(int i=h[x];i;i=ne[i])
    {
        int j=e[i];
        if(dfn[j]==0)
        {
            dfs(j);
            low[x]=min(low[x],low[j]);//连通且没被遍历过就改变low
        }
        else if(vi[j]) low[x]=min(low[x],low[j]);//如果被遍历过但在栈中也改变low
    }
    
    if(dfn[x]==low[x])//找到一个连通分量的头结点 出栈
    {
        while(!s.empty() && low[s.back()]==low[x])//一直出到没有一样的low值
        {
            int j=s.back();
            color[x].push_back(j);
            s.pop_back();
            vi[j]=false;
        }
    }
}
int main()
{
    add(1,2);
    add(2,3);
    add(3,4);
    add(3,5);
    add(4,5);
    add(4,2);
    add(1,6);
    add(6,7);
    add(7,1);
    
    for(int i=1;i<=7;i++)
    {
        if(!dfn[i])
        dfs(i);
    }
    
    for(int i=1;i<=7;i++)
    {
    for(int j=0;j 
割点
 
洛谷P3388【模板】割点（割顶） - 洛谷
 
#include 
#include 
#include 
#include 
using namespace std;
int dfn[200100],low[200100];
int e[250000],h[201000],ne[250000];
int idx,times,fa[201000];
int n,m,r;
set res;//set中有序且无重复点
void add(int a,int b)
{
    e[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
}
void dfs(int x)
{
    dfn[x]=low[x]=++times;
    int child=0;
    for(int i=h[x];i;i=ne[i])
    {
        int j=e[i];
        if(dfn[j]==0)
        {
            if(fa[x]==-1) child++;
            fa[j]=x;
            dfs(j);
            if(-1==fa[x] && child>=2) res.insert(x);
            if(-1!=fa[x] && low[j]>=dfn[x]) res.insert(x);
            low[x]=min(low[x],low[j]);
        }
        else if(j!=fa[x]) low[x]=min(low[x],dfn[j]);//非父子结点这里一定要更新为dfn!!卡了好几次
    }
}
    
int main()
{
    cin>>n>>m;
    for(int i=0;i::iterator j = res.begin(); j != res.end(); ++j)
    printf("%d ",*j);
    return 0;
}

 
LCA
 
#include 
#include 
#include 
using namespace std;
typedef pair PII;
int h[500010],ne[1000010],e[1000010];
bool vis[500010];
int res[500010],p[500010];
vector q[500010];
int n,m,s,idx;
void add(int a,int b)
{
    idx++;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
}

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void tarjan(int t)
{
    vis[t]=true;
    for(int i=h[t];i;i=ne[i])
    {
        int j=e[i];
        if(vis[j]) continue;
        tarjan(j);
        p[j]=find(t);
    }
    for(auto item : q[t])
    {
        int y=item.first,id=item.second;
        if(vis[y])
            res[id]=find(y);
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++)
    p[i]=i;
    for(int i=1;i