首页 > 代码库 > 100114J

100114J

2024-08-18 06:12:22   217人阅读

经过思考后，很明显，我们可以看出应该是求出两条最长的链，链是指挂在连通块上的技术分享

1,5可以称作一条链，但是，图里会有连通块，也就是环或者几个环相交在一起，这时就很难求链。这时，需要进行缩点。

缩点是把连通块变成一个点，大概是通过tarjan求出桥，也就是删掉这条边之后，图变得不连通，求出桥之后，把这些边删掉

然后通过dfs把每个连通块标记成一个颜色，也就是一个新的点，这时，所有的点都不联通，都有了新的编号，那些割点也是

然后就两次bfs求树的直径就可以了

#include<iostream>
#include<cstring>
#include<Vector>
#include<Queue>
#include<cstdio>
#define N 10010
using namespace std;
int n,m,all_edge=-1,time,x,cnt;
int to[20*N],next[20*N],head[20*N],color[20*N],num[N],d[N],low[N],dfn[N],cut[20*N];
queue<int>q;
vector<int>graph[N];
inline int min(int x,int y){return x<y?x:y;}
inline void ins(int u,int v){to[++all_edge]=v;next[all_edge]=head[u];head[u]=all_edge;}
inline void insert(int u,int v){ins(u,v);ins(v,u);}
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++time;
    for(int i=head[u];~i;i=next[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){cut[i]=cut[i^1]=1;}
        } else if(v!=fa)low[u]=min(low[u],low[v]);
    }
}
void dfs(int u)
{
    color[u]=cnt;
    for(int i=head[u];~i;i=next[i])
    {
        int v=to[i];
        if(!color[v]&&!cut[i]) dfs(v);
    }
}
void bfs(int point)
{
    int MAX=0;x=0;
    memset(d,-1,sizeof(d));
    q.push(point);
    d[point]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=0;i<graph[u].size();i++)
        {
            int v=graph[u][i];
            if(d[v]==-1)
            {
                d[v]=d[u]+1;
                q.push(v);
                if(d[v]>MAX){MAX=d[v];x=v;}
            }
        }
    }
    cout<<num[x]<<" ";
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cin>>n>>m;memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        insert(u,v);
    }
    tarjan(1,-1);
    for(int i=1;i<=n;i++) if(!color[i])
    {
        ++cnt;
        num[cnt]=i;
        dfs(i);
    }
    for(int i=0;i<all_edge;i+=2) if(cut[i])
    {
        int u=color[to[i^1]],v=color[to[i]];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
/*    cout<<"---------"<<endl;
    for(int i=1;i<=cnt;i++)
    { 
        cout<<"i="<<i<<":";
        for(int j=0;j<graph[i].size();j++)
        {
            cout<<graph[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"---------"<<endl;*/
    bfs(1);
    bfs(x);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

 

100114J


联系
我们