poj3694 & & hdu2460 (핸드폰 귀속 창고 버전의 tarjan)
문제: 가입한 변에 형성된 고리 안의 다리는 모두 존재하지 않는다.
#pragma comment(linker, "/STACK:10240000000000,10240000000000")
#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=110009;
const int M=210005;
int low[maxn];
int dfn[maxn];
int n,m;
vector<int>p[maxn];
stack<int>s;
int aa,bb;
int qu;
int vis[maxn];
int fa[maxn];
int b[maxn];
int tmp=1;
int ecnt;
struct Node
{
int u,v,next;
} edge[maxn*10];
int head[maxn];
int cnt;
void init()
{
tmp=1;
for(int i=1; i<=n; i++)
fa[i]=i;
memset(b,0,sizeof(b));
memset(vis,0,sizeof(vis));
cnt=1;
ecnt=0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
if(u==v)return;
edge[ecnt].u = u;
edge[ecnt].v = v;
edge[ecnt].next = head[u];
head[u] = ecnt++;
}
int tp;
int cur[maxn];
int st[maxn*10];
/*void tarjan(int u)
{
visit[u]=1;
dfn[u]=low[u]=tmp++;
for(int i=0; i<p[u].size(); i++)
{
int v=p[u][i];
if(!visit[v])
{
fa[v]=u;
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
{
cnt++;
b[v]=1;
}
}
else if(v != fa[u] && visit[v])
{
low[u]=min(low[u],dfn[v]);
}
}
}
*/
void tarjan()
{
for(int i = 1; i < maxn; ++ i)
cur[i] = head[i];
st[++tp] = 1;
while(tp)
{
int k = st[tp];
if(!vis[k])
{
dfn[k] = low[k] = tmp++;
vis[k] = 1;
}
for(; cur[k]!=-1; cur[k]=edge[cur[k]].next)
{
int v = edge[cur[k]].v;
if(!vis[v])
{
fa[v] = k;
break;
}
else if(vis[v]==1&&v!=fa[k])
low[k]=min(dfn[v],low[k]);
}
if((cur[k]==-1)&&tp>1)
{
low[st[tp-1]] = min(low[k],low[st[tp-1]]);
if(low[k]>dfn[st[tp-1]])
{
b[k] = 1;
cnt++;
}
}
if(cur[k]==-1)
{
vis[k] = 2;
tp--;
}
else st[++tp] = edge[cur[k]].v;
}
}
void LCA(int u,int v)
{
while(dfn[u]>dfn[v])
{
if(b[u])
{
cnt--;
b[u]=0;
}
u=fa[u];
}
while(dfn[v]>dfn[u])
{
if(b[v])
{
cnt--;
b[v]=0;
}
v=fa[v];
}
while(v!=u)
{
if(b[u])
{
cnt--;
b[u] = 0;
}
if(b[v])
{
cnt--;
b[v] = 0;
}
u = fa[u];
v = fa[v];
}
}
int main()
{
int cas=1;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n&&!m)break;
init();
for(int i=0; i<m; i++)
{
scanf("%d%d",&aa,&bb);
addedge(aa,bb);
addedge(bb,aa);
}
tarjan();
for(int i=1;i<=n;i++)
cout<<"i : "<<i<<" "<<dfn[i]<<endl;
cin>>qu;
cout<<"Case "<<cas++<<":"<<endl;
while(qu--)
{
scanf("%d%d",&aa,&bb);
LCA(aa,bb);
printf("%d
",cnt-1);
}
cout<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
poj 3624 Charm Bracelet(01 가방 입문문)Charm Bracelet Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10399 Accepted: 4667 Description Bessie has go...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.