hdu 2460 poj 3694 (더 블 연결 + LCA)
#pragma comment(linker, "/STACK:10240000000000,10240000000000")
#include<stdio.h>
#include<stack>
#include<string.h>
#define N 100010
using namespace std;
int belong[N],low[N],dfs[N],head[N],num,n,idx,ans,nume,vis[N];
struct edge
{
int st,ed,next;
}E[N*4],e[N*4];
void addedge(int x,int y)
{
E[num].st=x;
E[num].ed=y;
E[num].next=head[x];
head[x]=num++;
}
void Addedge(int x,int y)
{
e[nume].st=x;
e[nume].ed=y;
e[nume].next=head[x];
head[x]=nume++;
}
stack<int>Q;
void Tarjan(int u,int father)
{
int i,v,flag=0;
low[u]=dfs[u]=idx++;
Q.push(u);
for(i=head[u];i!=-1;i=E[i].next)
{
v=E[i].ed;
if(dfs[v]==-1)
{
Tarjan(v,u);
low[u]=low[u]>low[v]?low[v]:low[u];
}
else if(v==father)
{
if(flag)
low[u]=low[u]>dfs[v]?dfs[v]:low[u];
flag++;
}
else low[u]=low[u]>dfs[v]?dfs[v]:low[u];
}
if(low[u]==dfs[u])
{
do
{
v=Q.top();
Q.pop();
belong[v]=ans;
}while(v!=u);
ans++;
}
}
void dfs1(int u)
{
vis[u]=1;
int i,v;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].ed;
if(vis[v]==1)continue;
dfs[v]=dfs[u]+1;
low[v]=u;
dfs1(v);
}
}
void Lca(int x,int y)
{
int i;
if(dfs[x]<dfs[y])
{i=x;x=y;y=i;}
while(dfs[x]>dfs[y])
{
if(vis[x]==0)
{
vis[x]=1;
ans--;
}
x=low[x];
}
while(x!=y)
{
if(vis[x]==0)
{
vis[x]=1;
ans--;
}
if(vis[y]==0)
{
vis[y]=1;
ans--;
}
x=low[x];y=low[y];
}
}
int main()
{
int i,k,x,y,m,op=1;
while(scanf("%d%d",&n,&m),n||m)
{
memset(head,-1,sizeof(head));
num=0;
for(i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
memset(dfs,-1,sizeof(dfs));
idx=ans=0;
Tarjan(1,-1);
memset(head,-1,sizeof(head));
nume=0;
for(i=0;i<num;i++)
{
x=belong[E[i].st];
y=belong[E[i].ed];
if(x==y)continue;
Addedge(x,y);
Addedge(y,x);
}
memset(vis,0,sizeof(vis));
dfs[0]=0;
low[0]=0;
dfs1(0);
memset(vis,0,sizeof(vis));
printf("Case %d:
",op++);
scanf("%d",&k);
ans--;
while(k--)
{
scanf("%d%d",&x,&y);
Lca(belong[x],belong[y]);
printf("%d
",ans);
}
printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.