1 条题解

  • 0
    @ 2025-10-8 16:59:25
    #include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+10;
    vector<pair<int,int>>G[N];
    int id,cnt,dfn[N],low[N],cut[N];
    int root;int st,ed;
    void tarjan(int x,int in_id)
    {
        dfn[x]=low[x]=++id;
        int child=0;
        for(auto i:G[x])if(i.second!=in_id)
    	{
            int y=i.first,id=i.second;
            if(dfn[y]==0)
    		{
                tarjan(y,id);
                low[x]=min(low[x],low[y]);
                if(dfn[x]<=low[y])
    			{
                    child++;
                    if(x!=root||child>=2){
                        if(dfn[y]<=dfn[ed])  cut[x]=1;
                    }
                }
            }
            else low[x]=min(dfn[y],low[x]);
        }
    }
    int main()
    {
        int n;scanf("%d",&n);
        for(int i=1,x,y;scanf("%d%d",&x,&y);i++)
        {
            if(x==0 && y==0)break;
            G[x].push_back({y,i});
            G[y].push_back({x,i});
        }
    
        scanf("%d%d",&st,&ed);
        id=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); 
        memset(cut,0,sizeof(cut)); 
    	root=st,tarjan(st,0);
    	
        for(int i=1;i<=n;i++)if(cut[i]&&i!=st&&i!=ed){printf("%d\n",i);return 0;}
        puts("No solution");
        return 0;
    }
    
    • 1

    *【割点】求两点之间的割点[ZJOI2004] 嗅探器

    信息

    ID
    1883
    时间
    1000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    105
    已通过
    26
    上传者