Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

为啥就超时呢

Posted by qhq00 at 2020-03-17 11:25:06 on Problem 3694
```#define first f
#define second s
#define ll long long
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
//#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MOD=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
const double eps=1e-6;
const double PI=acos(-1.0);
const double e=2.718281828459;

struct node
{
int to,next;
}edge[maxn<<1];
int f[maxn],fa[maxn];

void add(int from,int to)
{
edge[cnt].to=to;
}
void init(int n)
{
for(int i=1;i<=n;i++){f[i]=i;}
}
int getfind(int x)
{
return f[x]==x?x:f[x]=getfind(f[x]);
}
bool _union(int x,int y)
{
int k1=getfind(x);
int k2=getfind(y);
if(k1!=k2){
f[k2]=k1;
return true;
}
return false;
}
void tarjin(int now,int pre)
{
low[now]=dfn[now]=++indx;
int to=edge[i].to;
if(!dfn[to]){
fa[to]=now;
tarjin(to,now);
low[now]=min(low[now],low[to]);
if(low[to]>dfn[now]){
ans++;
}
else{
_union(now,to);
}
}
else if(pre!=to){
low[now]=min(low[now],dfn[to]);
}
}
}
void LCA(int x,int y)
{
if(dfn[x]<dfn[y]){swap(x,y);}
while(dfn[x]>dfn[y]){
if(_union(fa[x],x)){
ans--;
}
x=fa[x];
}
while(x!=y){
if(_union(fa[y],y)){
ans--;
}
y=fa[y];
}
}
int main()
{
int n,m,u,v,q,T=0;
while(~scanf("%d%d",&n,&m)){
if(n==0&&m==0){break;}
init(n);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
}
tarjin(1,1);
scanf("%d",&q);
printf("Case %d:\n",++T);
for(int i=1;i<=q;i++){
scanf("%d%d",&u,&v);
LCA(u,v);printf("%d\n",ans);
}
printf("\n");
}
return 0;
}
```

Followed by: