UVALive – 7456 – Least Crucial Node(求图的割点)

2017年10月28日 0 条评论 12 次阅读 0 人点赞

题目链接:UVALive - 7456

题目大意:给出一个图,求标号最小的最大割点.(删除该点后,指定点#sink能到达的点数减少最多).

题目分析:

首先求出图中的所有的割点,然后由根节点开始进行DFS,求出每个割点的集合。

给出代码:

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
const int V=110;
int  edge[V][V];
int  bridge[V][V],cut[V];
int low[V],dfn[V],vis[V];
vector<int> g[V];
int marks[V];
int grades[V];
void init()
{
    memset(edge,0,sizeof(edge));
    memset(bridge,0,sizeof(bridge));
    memset(cut,0,sizeof(cut));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(vis,0,sizeof(vis));
    memset(marks,0,sizeof(marks));
}
void cut_bridge(int cur,int father,int dep,int n)
{
    vis[cur]=1;
    dfn[cur]=low[cur]=dep;
    int children=0;
    for(int i=0;i<n;++i)
        if(edge[cur][i])
    {
        if(i!=father&&1==vis[i])
        {
            if(dfn[i]<low[cur])
                low[cur]=dfn[i];
        }
        if(0==vis[i])
        {
            cut_bridge(i,cur,dep+1,n);
            children++;
            if(low[i]<low[cur])
                low[cur]=low[i];
            if((father==-1&&children>1)||(father!=-1&&low[i]>=dfn[cur]))
                cut[cur]=true;
            if(low[i]>dfn[cur])
            {
                bridge[cur][i]=bridge[i][cur]=true;
            }
        }
    }
    vis[cur]=2;
}
int dfs(int root)
{
    int n=g[root].size();
    marks[root]=1;
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int t=g[root][i];
        if(marks[t])
            continue;
        ans+=dfs(t);
    }
    grades[root]=ans;
    return ans+1;
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n&&n)
    {
        init();
        int mark;
        cin>>mark;
        mark--;
        int t;
        cin>>t;
        while(t--)
        {
            int a,b;
            cin>>a>>b;
            a--;
            b--;
            edge[a][b]=1;
            edge[b][a]=1;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        cut_bridge(0,-1,0,n);
        int ans=-1;
        dfs(mark);
        for(int i=0;i<n;i++)
        {
            if(cut[i]&&i!=mark)
            {
                if(ans==-1)
                    ans=i;
                else if(grades[ans]<grades[i])
                    ans=i;
            }
        }
        cout<<ans+1<<endl;
    }
    return 0;
  /* int n;
    cin>>n;
    int m=(int)n*log10(2);
    cout<<m<<endl;
    */
}

DLKKILL

这个人太懒什么东西都没留下

文章评论(0)