1 条题解
-
0
#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
信息
- ID
- 1883
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 105
- 已通过
- 26
- 上传者