强连通专题

POJ 2762 Going from u to v or from v to u?

题意:判断该图的任意两点是否可达

分析:tarjan后进行缩点,缩点后再建图,判断该图是否为单链式图形(只有一个叶结点)         判断能到达该点的节点个数是否等于bcnt

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
const int MN=2011;
vector<int>edge[MN];
vector<int>SCC[MN];
stack<int>s;

int low[MN],dfn[MN];
int instack[MN],stap[MN];
int belong[MN];
int num[MN];
int ind[MN];
int tp,p;
int bcnt;

void tarjan(int x)
{
    low[x]=dfn[x]=++tp;
    stap[++p]=x;
    instack[x]=1;
    for(int i=0;i<edge[x].size();i++)
    {
        int v=edge[x][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            if(low[x]>low[v])
               low[x]=low[v];
        }
        else if(instack[v] && dfn[v]<low[x])
               low[x]=dfn[v];
    }
    if(low[x]==dfn[x])
    {
        int top;
        do
        {
            top=stap[p];
            belong[top]=bcnt;
            instack[top]=0;
            p--;
        }while(x!=top);
        bcnt++;
    }
}

void topsort()
{
    memset(num,0,sizeof(num));
    int i,u,v;
    while(!s.empty())
        s.pop();
    for(int i=0;i<bcnt;i++)
        if(ind[i]==0)
        {
            s.push(i);
            num[i]++;
        }
    while(!s.empty())
    {
        u=s.top();
        s.pop();
        for(int i=0;i<SCC[u].size();i++)
        {
            v=SCC[u][i];
            if(--ind[v]==0)
            {
                s.push(v);
                num[v]=num[u]+1;
            }
        }
    }
}

int main()
{
    int T,n,m,i,a,b,j;
    scanf("%d",&T);
    while(T--)
    {
        bcnt=tp=p=0;
        scanf("%d%d",&n,&m);
        memset(dfn,-1,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(instack,0,sizeof(instack));
        memset(belong,0,sizeof(belong));
        memset(ind,0,sizeof(ind));
        for(i=1;i<=n;i++)
        {
            edge[i].clear();
            SCC[i].clear();
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            edge[a].push_back(b);
        }
        for(i=1;i<=n;i++)
        {
            if(dfn[i]==-1) tarjan(i);
        }
        for(i=1;i<=n;i++)
        {
            for(j=0;j<edge[i].size();j++)
            {
                int x=belong[i];
                int y=belong[edge[i][j]];
                if(x!=y)
                {
                     SCC[x].push_back(y);
                     ind[y]++;
                }
            }
        }
        topsort();
        int ans=-1;
        for(i=0;i<bcnt;i++)
        {
            ans=max(ans,num[i]);
        }
       // printf("%d\n",ans);
        if(bcnt==ans) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

POJ 2553  Popular Cows

题意:若牛A崇拜牛B,牛B崇拜牛C,则牛A崇拜牛C,问总共有多少只牛受到其他所有牛的崇拜

分析:若有环存在,则该环里的所有牛都互相崇拜,则可将环看成是一个点,后再构图,若想存在某个         点的牛收到其他所有牛的崇拜,则该图必定是单链式图形(只有一个叶结点)         tarjan缩点反向建图,然后只有一个入度为0

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
const int MN=11000;
vector<int>SCC[MN];
vector<int>edge[MN];
stack<int>s;

int low[MN],dfn[MN];
int instack[MN],stap[MN];
int belong[MN];
int num[MN];
int ind[MN];
int sum[MN];
int tp,p;
int bcnt;
int n,m;
int cnt;
int pos;

void tarjan(int x)
{
    low[x]=dfn[x]=++tp;
    stap[++p]=x;
    instack[x]=1;
    for(int i=0;i<edge[x].size();i++)
    {
        int v=edge[x][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            if(low[x]>low[v])
               low[x]=low[v];
        }
        else if(instack[v] && dfn[v]<low[x])
             low[x]=dfn[v];
    }
    if(low[x]==dfn[x])
    {
        int top;
        do
        {
            top=stap[p];
            belong[top]=bcnt;
            sum[bcnt]++;
            instack[top]=0;
            p--;
        }while(x!=top);
        bcnt++;
    }
}

void topsort()
{
    int u,v;
    stack<int>s;
    memset(num,0,sizeof(num));
    for(int i=0;i<bcnt;i++)
    {
        if(ind[i]==0)
        {
            s.push(i);
            pos=i;
            cnt++;
        }
    }
}

int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dfn,-1,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(instack,0,sizeof(instack));
        memset(belong,0,sizeof(belong));
        memset(ind,0,sizeof(ind));
        memset(sum,0,sizeof(sum));
        bcnt=tp=p=0;
        for(i=1;i<=n;i++)
        {
            edge[i].clear();
            SCC[i].clear();
        }
        for(i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            edge[a].push_back(b);
        }
        for(i=1;i<=n;i++)
        {
            if(dfn[i]==-1) tarjan(i);
        }
        for(i=1;i<=n;i++)
        {
            for(j=0;j<edge[i].size();j++)
            {
                int x=belong[i];
                int y=belong[edge[i][j]];
                if(x!=y)
                {
                    SCC[y].push_back(x);
                    ind[x]++;
                }
            }
        }
        int ans=0;
        cnt=0;
        topsort();
        if(cnt==1) printf("%d\n",sum[pos]);
        else printf("0\n");
    }
    return 0;
}

 POJ 2553  The Bottom of a Graph

题意:求出所有sink集合,sink集合的定义若v可达w,则w必定也可达v,求出所有的叶结点便可          而头节点不可以的原因是若v属于V,w不属于V,而v可达w,但是w不可达v,所以不可以          至于叶结点呢,v可达w,其中w必定都属于V集合

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MN=5010;
vector<int>SCC[MN];
vector<int>edge[MN];

int low[MN],dfn[MN];
int instack[MN],stap[MN];
int belong[MN];
int num[MN];
int ind[MN];
int rem[MN];
int tp,p;
int bcnt;
int n,m;
int cas;

void tarjan(int x)
{
    low[x]=dfn[x]=++tp;
    stap[++p]=x;
    instack[x]=1;
    for(int i=0; i<edge[x].size(); i++)
    {
        int v=edge[x][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            if(low[x]>low[v])
                low[x]=low[v];
        }
        else if(instack[v] && dfn[v]<low[x])
            low[x]=dfn[v];
    }
    if(low[x]==dfn[x])
    {
        int top;
        do
        {
            top=stap[p];
            belong[top]=bcnt;
            instack[top]=0;
            p--;
        }
        while(x!=top);
        bcnt++;
    }
}

void topsort()
{
    for(int i=0; i<bcnt; i++)
    {
        if(ind[i]==0)
        {
            for(int j=1; j<=n; j++)
            {
                if(belong[j]==i) rem[cas++]=j;
            }
        }
    }
}

bool cmp(int a,int b)
{
    return a<b;
}

int main()
{
    int i,w,v,j;
    while(scanf("%d",&n) && n)
    {
        scanf("%d",&m);
        tp=p=bcnt=cas=0;
        memset(dfn,-1,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(instack,0,sizeof(instack));
        memset(belong,0,sizeof(belong));
        memset(ind,0,sizeof(ind));
        for(i=0; i<=n; i++)
        {
            edge[i].clear();
            SCC[i].clear();
        }
        for(i=0; i<m; i++)
        {
            scanf("%d%d",&w,&v);
            edge[w].push_back(v);
        }
        for(i=1; i<=n; i++)
        {
            if(dfn[i]==-1) tarjan(i);
        }
        for(i=1; i<=n; i++)
        {
            for(j=0; j<edge[i].size(); j++)
            {
                int x=belong[i];
                int y=belong[edge[i][j]];
                if(x!=y)
                {
                    SCC[y].push_back(x);
                    ind[x]++;
                }
            }
        }
        topsort();
        sort(rem,rem+cas,cmp);
        printf("%d",rem[0]);
        for(i=1; i<cas; i++)
        {
            printf(" %d",rem[i]);
        }
        printf("\n");

    }
    return 0;
}

 POJ 1523 SPF

题意: 找出割点,且将割点拿掉后,存在几个连通分量 分析:   构建一棵dfs树,序列dfn[i]为深度优先数,表示dfs时访问i节点的序号,low[i]表示从i节点出发能访问到的最小的深度优先数。             当且仅当节点u满足如下两个条件之一时,u为割点:             1.u为dfs树的根,且u至少有两个子节点。             2.u不是dfs树的根,至少存在一个节点v是u的子节点,且low[v]>=dfn[u]。             若u为割点,记subnets[u]为u的子节点数,则去掉u后,图被分成subnets[u]+1个部分(每个子节点的部分和u的祖先的部分),若u为dfs树的根,则分                                                   成subnets[u]个部分(根节点没有祖先)。         以上全部算法均在dfs过程中完成。

割点模板

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MN=1111;

struct Edge
{
    int to,next;
} edge[MN<<2];
int dfn[MN];
int low[MN];
int head[MN<<2];
int subnet[MN];
int E;
int tp;
int root;
int vis[MN];

void Init()
{
    memset(dfn,-1,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(head,-1,sizeof(head));
    memset(subnet,0,sizeof(subnet));
    memset(vis,0,sizeof(vis));
    E=tp=0;
}

void Add(int a,int b)
{
    edge[E].to=b;
    edge[E].next=head[a];
    head[a]=E++;
}

void tarjan(int u,int fa){  //割点模板
    int son=0;
    vis[u]=1;
    dfn[u]=low[u]=++tp;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(vis[v]==1 && v!=fa)
            low[u]=min(low[u],dfn[v]);
        if(!vis[v]){
            tarjan(v,u);
            son++;
            low[u]=min(low[u],low[v]);
            if((u==root && son>1) || (u!=root && dfn[u]<=low[v]))
                subnet[u]++;   //cut[u] 表示u这个点割边数
        }
    }
    vis[u]=2;
}

int main()
{
    int i,cas=1,n,a,b,nodes;
    while(scanf("%d",&n) && n)
    {
        nodes=n;
        Init();
        scanf("%d",&b);
        Add(n,b);
        Add(b,n);
        while(scanf("%d",&a) && a)
        {
            scanf("%d",&b);
            if(nodes<a) nodes=a;
            if(nodes<b) nodes=b;
            Add(a,b);
            Add(b,a);
        }
        for(i=1; i<=nodes; i++)
        {
            if(dfn[i]==-1)
            {root=i;
                tarjan(i,-1);
                
            }
        }
        int flag=0;
        printf("Network #%d\n",cas++);
        for(i=1; i<=nodes; i++)
        {
            if(subnet[i]>=1)
            {
                flag=1;
                printf("  SPF node %d leaves %d subnets\n",i,subnet[i]+1);
            }
        }
        if(flag==0) printf("  No SPF nodes\n");
        puts("");
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏fixzd

redis系列:通过通讯录案例学习hash命令

这一篇文章将讲述Redis中的hash类型命令,同样也是通过demo来讲述,其他部分这里就不在赘述了。

13210
来自专栏数据结构与算法

洛谷P2792 [JSOI2008]小店购物(最小树形图)

一开始的思路:新建一个虚点向每个点连边,再加上题面中给出的边,边权均为大小*需要购买的数量

10210
来自专栏社区的朋友们

理解 B+ 树算法

最近有接触到 b+ 树,花了点时间,顺便总结梳理下方便后续翻阅;时间仓促,且文中多是个人的理解,仅供参考。

1.2K00
来自专栏java沉淀

java实现Excel导入(迭代一)

21720
来自专栏JAVA高级架构开发

Java 11 正式发布,这 8 个逆天新特性教你写出更牛逼的代码

美国时间 09 月 25 日,Oralce 正式发布了 Java 11,这是据 Java 8 以后支持的首个长期版本。

24300
来自专栏来自地球男人的部落格

[LeetCode] 134. Gas Station

【原题】 There are N gas stations along a circular route, where the amount of gas...

21380
来自专栏测试驿栈

Jmeter(十二)_打印时间戳

  年: yyyy 月:MM 日:dd   时: HH 分: mm 秒:ss

23040
来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:练习——单身狗租赁系统

42340
来自专栏非典型技术宅

Swift实践:使用CoreData存储多种数据类的通讯录1. CoreData支持存储数据类型2. 使用CoreData存储多种数据类的通讯录3. Codable

22830
来自专栏杂烩

jedis针对三种redis工作模式的连接方式

BinaryJedisCluster.java是为了让jedis支持byte数组形式value重写的一个类,参考网上文档,记不得来源了。以下是代码(部分):

19220

扫码关注云+社区

领取腾讯云代金券