救命,最后一个点t了
查看原帖
救命,最后一个点t了
308583
跳跳谷hj楼主2021/8/11 17:10
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
vector <int>vec[N];
int l,dfn[N],low[N],k,serv,indx,n,ls,p;
int cetp1,cetp2;
bool iscp[N],vis[N];
void find_CutPoint(int u,int fa){
	int child=0;
    dfn[u]=low[u]=++indx;
    for(int i=0;i<vec[u].size() ;i++){
        int v=vec[u][i];
        if(v==fa)continue;
        if(!dfn[v]){
            child++;
            find_CutPoint(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])iscp[u]=true;
        }else low[u]=min(low[u],dfn[v]);
    }
    if(fa<0&&child==1)iscp[u]=false;
}
void dfs(int u){
    vis[u]=true;
    for(int i=0;i<vec[u].size();i++){
        int v=vec[u][i];
        if(vis[v]==true)continue;
        dfs(v);
    }
}
int main(){
	scanf("%d",&serv);
    while(1){
    	scanf("%d%d",&n,&p);
    	if(n==0&&p==0)break;
		vec[n].push_back(p);
        vec[p].push_back(n);
    }
    scanf("%d%d",&cetp1,&cetp2);
    find_CutPoint(cetp1,-1);
    for(int i=1;i<=serv;i++){
        if(i==cetp1||i==cetp2||!iscp[i])continue;
        memset(vis,0,sizeof(vis));
        vis[i]=true;
        dfs(cetp1);
        if(!vis[cetp2]){
            printf("%d",i);
            return 0;
        }
    }
	printf("No solution");
}

有没有奆佬来看一下啊啊啊

2021/8/11 17:10
加载中...