CF1000E We Need More Bosses

2018-09-23 17:37:30


题意:给定无向图,问任意找 $s$ 到 $t$ ,路径上必须经过的边最多有几条

缩点之后找树的直径就好了qwq

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
using namespace std;
const int N=3e5+5;
struct node
{
    int to,nxt;
}edge[N<<1];
int n,m,num,head[N],dfn[N],low[N],stack[N];
int top,cnt,bel[N],tot,fr[N],to[N],dis[N],ans;
bool exist[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]}; head[from]=num;
    edge[++num]=(node){from,head[to]}; head[to]=num;
}
void tarjan(int k,int fa)
{
    int temp;
    dfn[k]=low[k]=++cnt;
    stack[++top]=k; exist[k]=1;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==fa) continue;
        if (!dfn[v])
        {
            tarjan(v,k);
            low[k]=min(low[k],low[v]);
        }
        else if (exist[v])
          low[k]=min(low[k],dfn[v]);
    }
    if (dfn[k]==low[k])
    {
        ++tot;
        do
        {
            temp=stack[top--];
            exist[temp]=0;
            bel[temp]=tot;
        }while (temp!=k);
    }
}
void dfs(int k,int fa)
{
    dis[k]=dis[fa]+1;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v!=fa) dfs(v,k);
    }
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=m;i++)
    {
        fr[i]=read(),to[i]=read();
        add_edge(fr[i],to[i]);
    }
    for (reg int i=1;i<=n;i++) if (!dfn[i]) tarjan(i,i);
    memset(head,0,sizeof(head)); num=0;
    for (reg int i=1;i<=m;i++)
      if (bel[fr[i]]!=bel[to[i]]) add_edge(bel[fr[i]],bel[to[i]]);
    dfs(1,0); int pos=1;
    for (reg int i=2;i<=tot;i++) if (dis[i]>dis[pos]) pos=i;
    dfs(pos,0);
    for (reg int i=1;i<=tot;i++) ans=max(ans,dis[i]);
    printf("%d\n",ans-1);
    return 0;   
}