美文网首页
连通图

连通图

作者: fo0Old | 来源:发表于2017-04-20 23:00 被阅读0次

    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;
}

    相关文章

      网友评论

          本文标题：连通图

          本文链接：https://www.haomeiwen.com/subject/xsjrzttx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|连通图|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！