连通图

Strongly Connected Componenet

namespace Graph
{
    const int __=2e5+5;
    int n,v[__];//点权
    vector<int>G[__];

    void init(int _n)
    {
        n=_n;
        for(int i=1;i<=n;++i)
            G[i].clear();
    }

    void add_edge(int x,int y)//有向边
    {
        G[x].push_back(y);
    }
}

namespace SCC
{
    const int __=2e5+5;
    vector<int>G[__];//缩点后注意重边有影响使用set
    int n,idx,dfn[__],low[__],bel[__],s[__];//栈
    ll v[__];//缩点后的点权

    int dfs(int x)
    {
        if(dfn[x])return dfn[x];
        s[++*s]=x;
        dfn[x]=low[x]=++idx;
        for(int y:Graph::G[x])
            if(!bel[y])
                low[x]=min(low[x],dfs(y));
        if(low[x]==dfn[x])
            for(bel[x]=++n,v[n]=0;;--*s)
            {
                v[n]+=Graph::v[s[*s]];
                if(s[*s]==x){--*s;break;}
                else bel[s[*s]]=n;
            }
        return low[x];
    }

    void tarjan()//注意一个点的特判
    {
        idx=n=*s=0;
        for(int i=1;i<=Graph::n;++i)
            if(!dfn[i])dfs(i);
        for(int i=1;i<=Graph::n;++i)
            for(int y:Graph::G[i])
                if(bel[i]!=bel[y])
                    G[bel[i]].push_back(bel[y]);
    }

    void clear()
    {
        for(int i=1;i<=Graph::n;++i)
        {
            dfn[i]=bel[i]=0;
            G[i].clear();
        }
    }

    void print()
    {
        for(int i=1;i<=Graph::n;++i)
            printf("bel[%d]=%d\n",i,bel[i]);
        for(int i=1;i<=n;++i)
        {
            printf("%d:",i);
            for(int x:G[i])
                pf(" %d",x);
            putchar('\n');
        }
    }
}

割点(tarjan):

vector<int>G[105];
int low[105],dfn[105],cut[105],cont=1,ans=0;

void dfs(int fa,int x)
{
    int son=0;
    dfn[x]=low[x]=cont++;
    int len=G[x].size();
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i];
        if(nex==fa)continue;
        if(!dfn[nex])
        {
            son++;
            dfs(x,nex);
            low[x]=min(low[x],low[nex]);
            if(low[nex]>=dfn[x]&&fa!=-1&&!cut[x])
            {
                cut[x]=1;
                ans++;
            }
        }
        else low[x]=min(low[x],dfn[nex]);
    }
    if(fa==-1&&son>1)
    {
        cut[x]=1;
        ans++;
    }
}

题目链接:Network(求割点个数)

tarjan:

vector<int>G[105];
int low[105],dfn[105],cut[105],cont=1,ans=0;

void dfs(int fa,int x)
{
    int son=0;
    dfn[x]=low[x]=cont++;
    int len=G[x].size();
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i];
        if(nex==fa)continue;
        if(!dfn[nex])
        {
            son++;
            dfs(x,nex);
            low[x]=min(low[x],low[nex]);
            if(low[nex]>=dfn[x]&&fa!=-1&&!cut[x])
            {
                cut[x]=1;
                ans++;
            }
        }
        else low[x]=min(low[x],dfn[nex]);
    }
    if(fa==-1&&son>1)
    {
        cut[x]=1;
        ans++;
    }
}

void init(void)
{
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(cut,0,sizeof(cut));
    cont=1;     ans=0;
}

int main()
{
    int n,x,y;
    char ch;
    while(~scanf("%d",&n)&&n)
    {
        init();
        while(~scanf("%d",&x)&&x)
            while((ch=getchar())!='\n')
            {
                scanf("%d",&y);
                G[x].push_back(y);
                G[y].push_back(x);
            }
        for(int i=1; i<=n; i++)
            if(!dfn[i])dfs(-1,i);
        printf("%d\n",ans);
        for(int i=1; i<=n; i++)
            G[i].clear();
    }
    return 0;
}

题目链接:割点(求割点个数以及割点)

tarjan:

int low[100005],dfn[100005],cut[100005],cont=1,ans=0;
vector<int>G[100005];

void dfs(int fa,int x)
{
    int son=0;
    dfn[x]=low[x]=cont++;
    int len=G[x].size();
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i];
        if(nex==fa)continue;
        if(!dfn[nex])
        {
            son++;
            dfs(x,nex);
            low[x]=min(low[x],low[nex]);
            if(low[nex]>=dfn[x]&&fa!=-1&&!cut[x])
            {
                cut[x]=1;
                ans++;
            }
        }
        else low[x]=min(low[x],dfn[nex]);
    }
    if(fa==-1&&son>1)
    {
        cut[x]=1;
        ans++;
    }
}

int main()
{
    int m,n,x,y;
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!dfn[x])dfs(-1,i);
    printf("%d\n",ans);
    int res=0;
    for(int i=1;i<=n;i++)
        if(cut[i])
        {
            if(res!=0)printf(" ");
            res=1;
            printf("%d",i);
        }
    return 0;
}

割边(tarjan):

int low[100005],dfn[100005],cont,ans;
vector<int>G[100005];
vector<pair<int,int> >bri;
void dfs(int fa,int x)
{
    dfn[x]=low[x]=cont++;
    int len=G[x].size();
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i];
        if(nex==fa)continue;
        if(!dfn[nex])
        {
            dfs(x,nex);
            low[x]=min(low[x],low[nex]);
            if(low[nex]>dfn[x])
            {
                if(nex>x)bri.push_back(make_pair(x,nex));
                else bri.push_back(make_pair(nex,x));
                ans++;
            }
        }
        else low[x]=min(low[x],dfn[nex]);
    }
}

题目链接:Critical Links

tarjan:

int low[100005],dfn[100005],cont,ans;
vector<int>G[100005];
vector<pair<int,int> >bri;

void dfs(int fa,int x)
{
    dfn[x]=low[x]=cont++;
    int len=G[x].size();
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i];
        if(nex==fa)continue;
        if(!dfn[nex])
        {
            dfs(x,nex);
            low[x]=min(low[x],low[nex]);
            if(low[nex]>dfn[x])
            {
                if(nex>x)bri.push_back(make_pair(x,nex));
                else bri.push_back(make_pair(nex,x));
                ans++;
            }
        }
        else low[x]=min(low[x],dfn[nex]);
    }
}

void init(void)
{
    bri.clear();
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    cont=1;
    ans=0;
}

int main()
{
    int T,n,x,y,m;
    while(~scanf("%d",&T))
    {
        init();
        n=T;
        while(T--)
        {
            scanf("%d (%d)",&x,&m);
            for(int i=0; i<m; i++)
            {
                scanf("%d",&y);
                G[x+1].push_back(y+1);
                G[y+1].push_back(x+1);
            }
        }
        for(int i=1; i<=n; i++)
            if(!dfn[i])dfs(-1,i);
        printf("%d critical links\n",ans);
        sort(bri.begin(),bri.end());
        int len=bri.size();
        for(int i=0;i<len;i++)
            printf("%d - %d\n",bri[i].first-1,bri[i].second-1);
        printf("\n");
        for(int i=1;i<=n;i++)
            G[i].clear();
    }
    return 0;
}

题目链接:割边与割点

tarjan:

int low[20005],dfn[20005],cut[20005],cont,ans;
vector<int>G[20005];
vector<pair<int,int> >bri;
void dfs(int fa,int x)
{
    int son=0;
    dfn[x]=low[x]=cont++;
    int len=G[x].size();
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i];
        if(nex==fa)continue;
        if(!dfn[nex])
        {
            son++;
            dfs(x,nex);
            low[x]=min(low[x],low[nex]);
            if(low[nex]>dfn[x])  //桥
                if(nex>x)bri.push_back(make_pair(x,nex));
                else bri.push_back(make_pair(nex,x));
            if(low[nex]>=dfn[x]&&fa!=-1&&!cut[x])   //割点
            {
                ans++;
                cut[x]=1;
            }
        }
        else low[x]=min(low[x],dfn[nex]);
    }
    if(fa==-1&&son>1)   //根节点割点判定
    {
        cut[x]=1;
        ans++;
    }
}
void init(void)
{
    bri.clear();
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    cont=1;
    ans=0;
}
int main()
{
    int n,m,x,y;
    init();
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!dfn[i])dfs(-1,i);
    sort(bri.begin(),bri.end());
    bool flag=false;
    if(ans==0)printf("Null\n");
    else
        for(int i=1; i<=n; i++)
            if(cut[i])
            {
                if(flag)printf(" ");
                printf("%d",i);
                flag=true;
            }
    printf("\n");
    int len=bri.size();
    for(int i=0; i<len; i++)
        printf("%d %d\n",bri[i].first,bri[i].second);
    return 0;
}

强联通分量:

题目链接:迷宫城堡

Kosaraju:

vector<int>G[10005];   //正向边
vector<int>Gr[10005];  //反向边
stack<int>S;
int vis[10005];
int m,n;

void dfs_normal(int node)
{
    vis[node]=1;
    int len=G[node].size();
    for(int i=0; i<len; i++)
        if(!vis[G[node][i]])dfs_normal(G[node][i]);
    S.push(node);
}

void dfs_reverse(int node)
{
    vis[node]=1;
    int len=Gr[node].size();
    for(int i=0; i<len; i++)
        if(!vis[Gr[node][i]])dfs_reverse(Gr[node][i]);
}

int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        if(m==0&&n==0)return 0;
        int x,y;
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            Gr[y].push_back(x);
        }
        for(int i=1; i<=m; i++)
        {
            if(!vis[i])dfs_normal(i);
            vis[i]=0;
        }
        int cont=0;
        while(!S.empty())
        {
            int t=S.top();
            S.pop();
            if(!vis[t])
            {
                dfs_reverse(t);
                cont++;
            }
        }
        if(cont==1)printf("Yes\n");
        else printf("No\n");
        for(int i=1; i<=m; i++)
        {
            G[i].clear();
            Gr[i].clear();
            vis[i]=0;
        }
    }
    return 0;
}

题目链接:The Cow Prom

tarjan:

vector<int>G[50005];
int vis[50005];
int dfn[50005];
int low[50005];
int cont=1;
int n,m,ans=0;
stack<int>S;

void dfs(int x)
{
    dfn[x]=low[x]=cont++;
    S.push(x);vis[x]=1;
    int len=G[x].size();
    for(int i=0; i<len; i++)
        if(!vis[G[x][i]])
        {
            dfs(G[x][i]);
            low[x]=min(low[x],low[G[x][i]]);
        }
        else if(vis[G[x][i]]==1)
            low[x]=min(low[x],dfn[G[x][i]]);
    if(dfn[x]==low[x])
    {
        int res=0;
        while(1)
        {
            int t=S.top();
            S.pop();
            vis[t]=2;  //访问完成
            res++;
            if(x==t)break;
        }
        if(res>1)ans++;
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=0; i<m; i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
    }
    for(int i=1; i<=n; i++)
        if(!vis[i])dfs(i);
    printf("%d\n",ans);
    return 0;
}

双联通分量:

题目链接:边的双连通分量

tarjan:

int low[20005],dfn[20005],cont,ans;
int bel[20005],minn[20005];
vector<int>G[20005];
stack<int>S;

void dfs(int fa,int x)
{
    dfn[x]=low[x]=cont++;
    S.push(x);
    int len=G[x].size();
    for(int i=0;i<len;i++)
    {
        int nex=G[x][i];
        if(nex==fa)continue;
        if(!dfn[nex])
        {
            dfs(x,nex);
            low[x]=min(low[x],low[nex]);
        }
        else low[x]=min(low[x],dfn[nex]);
    }
    if(low[x]==dfn[x])
    {
        minn[++ans]=inf;
        while(1)
        {
            int t=S.top();
            S.pop();
            minn[ans]=min(minn[ans],t);
            bel[t]=ans;
            if(t==x)break;
        }
    }
}

void init(void)
{
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(bel,0,sizeof(bel));
    cont=1;
    ans=0;
}

int main()
{
    int n,m,x,y;
    init();
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])dfs(-1,i);
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
    {
        printf("%d",minn[bel[i]]);
        if(i!=n)printf(" ");
        else printf("\n");
    }
    return 0;
}

题目链接:点的双连通分量

tarjan:

struct node
{
    int nex,id;
} t;

struct edge
{
    int now,nex,id;
} temp;

int low[20005],dfn[20005],bel[100005],minn[100005],cont,ans;
bool vis[100005];
stack<edge>S;
vector<node>G[20005];

void dfs(int fa,int x)
{
    int son=0;
    dfn[x]=low[x]=cont++;
    int len=G[x].size();
    for(int i=0; i<len; i++)
    {
        int nex=G[x][i].nex;
        int id=G[x][i].id;
        if(nex==fa||vis[id])continue;
        temp.id=id,     temp.now=x,     temp.nex=nex;
        S.push(temp);
        if(!dfn[nex])
        {
            son++;
            dfs(x,nex);
            low[x]=min(low[x],low[nex]);
            if((low[nex]>=dfn[x]&&fa!=-1)||(son>1&&fa==-1))
            {
                ans++;
                while(1)
                {
                    temp=S.top();
                    S.pop();
                    bel[temp.id]=ans;
                    minn[ans]=min(minn[ans],temp.id);
                    vis[temp.id]=true;
                    if(temp.now==x&&temp.nex==nex)break;
                }
            }
        }
        else low[x]=min(low[x],dfn[nex]);
    }
}

void init(int n)
{
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(bel,0,sizeof(bel));
    memset(vis,false,sizeof(vis));
    cont=1;
    ans=0;
    for(int i=1; i<=n; i++)
        minn[i]=inf;
}

int main()
{
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    init(m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        t.id=i;
        t.nex=y;
        G[x].push_back(t);
        t.nex=x;
        G[y].push_back(t);
    }
    for(int i=1; i<=n; i++)
        if(!dfn[i])dfs(-1,i);
    ans++;
    while(!S.empty())
    {
        temp=S.top();
        S.pop();
        bel[temp.id]=ans;
        minn[ans]=min(minn[ans],temp.id);
    }
    printf("%d\n",ans);
    for(int i=1; i<=m; i++)
        printf("%d ",minn[bel[i]]);
    return 0;
}

最后编辑于：2019.04.24 15:23:27

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 215,723评论 6赞 498
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,003评论 3赞 391
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 161,512评论 0赞 351
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,825评论 1赞 290
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,874评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,841评论 1赞 295
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,812评论 3赞 416
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,582评论 0赞 271
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,033评论 1赞 308
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,309评论 2赞 331
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,450评论 1赞 345
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,158评论 5赞 341
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,789评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,409评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,609评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,440评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,357评论 2赞 352

连通图

Strongly Connected Componenet

割点(tarjan):

题目链接:Network(求割点个数)

tarjan:

题目链接:割点(求割点个数以及割点)

tarjan:

割边(tarjan):

题目链接:Critical Links

tarjan:

题目链接:割边与割点

tarjan:

强联通分量:

题目链接:迷宫城堡

Kosaraju:

题目链接:The Cow Prom

tarjan:

双联通分量:

题目链接:边的双连通分量

tarjan:

题目链接:点的双连通分量

tarjan:

推荐阅读更多精彩内容