12389. 割点

ゝ一纸荒年。 2023-07-17 05:57 1阅读 0赞

# 12389. 割点 #

n个顶点m条边，请求割点

## 输入格式: ##

第一行给定三个整数 n，m 。n 个城镇，m 条道路(双向道路)。接下来给出 m 行，每行两个正整数表示这两个城镇之间有边相连。

## 输出格式: ##

一个整数，有几个关键城市。

样例 1 :

输入:  
9 11  
1 2  
2 3  
1 3  
3 5  
4 3  
5 6  
4 6  
6 8  
6 7  
7 8  
8 9  
输出:  
3  
说明:  
3 6 8是关键城市

https://www.acoj.com/problems/12389

#include <cstdio>
    #include <vector>
    #include <cstring>
    
    using namespace std;
    
    const int max_n = 100000+10;
    
    int n,m;
    vector<int> g[max_n];
    int num[max_n],low[max_n],flag[max_n],time_index,root;
    
    void dfs(int cur,int fa)
    {
        
        int child=0;
    
        ++time_index;
        num[cur]=time_index;
        low[cur]=time_index;
    
        for(int i=0;i<g[cur].size();++i)
        {
        
            int v=g[cur][i];
            if(num[v]==0)
            {
        
                ++child;
                dfs(v,cur);
                low[cur]=min(low[v],low[cur]);
                if(cur!=root && num[cur]<=low[v])
                {
        
                    flag[cur]=1;
                }
                if(cur==root && child==2)
                {
        
                    flag[cur]=1;
                }
            }
            else if(v!=fa)
            {
        
                low[cur]=min(num[v],low[cur]);
            }
        }
    
    }
    
    void solve()
    {
        
        time_index=0;
        root=1;
        memset(num,0,sizeof(num));
        memset(flag,0,sizeof(flag));
    
        dfs(1,1);
    
        int ans=0;
        for(int i=1;i<=n;++i)
        {
        
            if(flag[i])
            {
        
                //printf("%d ",i);
                ++ans;
            }
        }
        printf("%d",ans);
    }
    
    int main()
    {
        
        scanf("%d %d",&n,&m);
        int a,b;
        for(int i=0;i<m;++i)
        {
        
            scanf("%d %d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
    
        solve();
    
        return 0;
    }