[cogs8]备用交换机

发表于 2017-08-12   |   分类于 图论

题目

【问题描述】
n个城市之间有通讯网络,每个城市都有通讯交换机,直接或间接与其它城市连接。因电子设备容易损坏,需给通讯点配备备用交换机。但备用交换机数量有限,不能全部配备,只能给部分重要城市配置。于是规定:如果某个城市由于交换机损坏,不仅本城市通讯中断,还造成其它城市通讯中断,则配备备用交换机。请你根据城市线路情况,计算需配备备用交换机的城市个数,及需配备备用交换机城市的编号。
【输入格式】
输入文件有若干行
第一行,一个整数n,表示共有n个城市(2<=n<=100)
下面有若干行,每行2个数a、b,a、b是城市编号,表示a与b之间有直接通讯线路。
【输出格式】
输出文件有若干行
第一行,1个整数m,表示需m个备用交换机,下面有m行,每行有一个整数,表示需配备交换机的城市编号,输出顺序按编号由小到大。如果没有城市需配备备用交换机则输出0。

题目的意思就是求割点
根据tarjan算法,如果有一条边为u->v
当low[v]>=dfn[u]的时候,u就是割点
但有个特殊情况就是u为根节点的时候
不难发现如果只有这个判断条件一个三角形就可以破解这个做法了
所以tarjan里面还有一个判断条件就是
当fa[v]==root的时候,累加一下rootson
这样当要判断root是否为割点的时候只需要if(rootson>1)

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int _maxn=110;
int dfn[_maxn],n,low[_maxn],ans[_maxn],e,anss,rootson;
bool g[_maxn][_maxn],vis[_maxn],book[_maxn];
void tarjan(int u,int fa,int root){
    dfn[u]=low[u]=++e;
    vis[u]=true;
    if(fa==root)
        rootson++;
    if(fa==-1)
        rootson=0;
    for(int i=1;i<=n;i++){
        if(g[u][i] && i!=fa){
            if(vis[i])    low[u]=min(low[u],dfn[i]);
            else{
                tarjan(i,u,root);
                low[u]=min(low[u],low[i]);
                if(low[i]>=dfn[u] && !book[u]){
                    if(u==root && rootson==1)
                        continue;
                    book[u]=true;
                    ans[++anss]=u;
                }
            }
        }
    }
    return;
}
int main(){
    freopen("gd.in","r",stdin);
    freopen("gd.out","w",stdout);
    scanf("%d",&n);
    int x,y;
    while(scanf("%d%d",&x,&y)==2)
        g[x][y]=g[y][x]=true;
    for(int i=1;i<=n;i++)
        if(!vis[i])
            tarjan(i,-1,i);
    sort(ans+1,ans+anss+1);
    printf("%d\n",anss);
    for(int i=1;i<=anss;i++)
        printf("%d\n",ans[i]);
    return 0;
}

已有 2 条评论


  1. 志平

    好久没写过C代码了,想当年也是想从事嵌入式的,可惜没坚持下去。

    志平 September 5th, 2017 at 09:14 pm回复
    1. helloworld

      嵌入式也是门有趣的学科

      helloworld November 7th, 2017 at 09:21 pm回复

发表新评论

© 2017 Powered by Typecho & Theme Quark