poj 3895 Cycles of Lanes 수정 tarjan 알고리즘 구도 중 최대 링
변 권 이 모두 1 인 무 방향 도 를 주 고 그림 의 최대 고 리 를 구하 세 요.
분석:
tarjan 알고리즘 은 보통 강 한 연결 분량 에 사 용 됩 니 다. 그림 의 각 강 한 연결 분량 을 순서대로 방문 합 니 다. 이 문 제 는 최대 링 을 요구 합 니 다. 링 도 강 한 연결 분량 의 일부분 이기 때문에 각 점 에서 다른 점 을 방문 할 때 시간 스탬프 를 수정 하여 각 링 의 시간 스탬프 연속 항목 에 도달 할 수 있 습 니 다. 그러면 한 스 택 의 노드 를 방문 할 때 최대 링 을 직접 업데이트 할 수 있 습 니 다.같은 사고 에 따라 변 권 이 임 의적 이 더 라 도 최대 고리 나 최소 고 리 를 구 할 수 있다.
코드:
//poj 3895
//sep9
#include
#include
#include
using namespace std;
const int maxN=4500;
vector g[maxN];
stack s;
int dfn[maxN],low[maxN],ins[maxN],belong[maxN];
int n,m,ans,t,cnt;
void tarjan(int fa,int u)
{
dfn[u]=low[u]=++t;
ins[u]=1;
s.push(u);
for(int i=g[u].size()-1;i>=0;--i){
int v=g[u][i];
if(fa==v)
continue;
if(!dfn[v]){
int tmp=t;
tarjan(u,v);
t=tmp;
low[u]=min(low[u],low[v]);
}else if(ins[v]==1){
low[u]=min(low[u],dfn[v]);
ans=max(ans,dfn[u]-dfn[v]+1);
}
}
int k;
if(low[u]==dfn[u]){
++cnt;
do{
k=s.top();
s.pop();
ins[k]=0;
belong[k]=cnt;
}while(dfn[k]!=low[k]);
}
}
int main()
{
int cases;
scanf("%d",&cases);
while(cases--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
g[i].clear();
while(m--){
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
t=cnt=ans=0;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(ins,0,sizeof(ins));
while(!s.empty()) s.pop();
tarjan(-1,1);
printf("%d
",ans);
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1874: 원활 한 공사 계속 [Dijkstra & SPFA & Floyd]모 성 은 여러 해 동안 의 원활 한 공사 계획 을 실행 한 후에 마침내 많은 길 을 건설 하 였 다.길 을 많이 건 너 지 않 아 도 좋 지 않다. 한 도시 에서 다른 도시 로 갈 때마다 여러 가지 도로 방안 을 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
