We Need More Bosses CodeForces - 1000E（缩点 建图 求桥 求直径）

题意：

　　就是求桥最多的一条路

解析：

　　先求连通分量的个数 然后缩点建图  求直径即可

　

#include <bits/stdc++.h>

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

const int maxn = 1e6+, INF = 0x7fffffff;

vector<int> G[maxn<<];

int pre[maxn<<], lowlink[maxn<<], sccno[maxn<<], dfs_clock, scc_cnt, d[maxn<<], vis[maxn<<];

stack<int> S;

int n, m, maxway, pos;

map<int, int> w[maxn<<];

int head[maxn<<], cnt, ans;

struct node

{

    int u, v, next;

}Node[maxn<<];

void add_(int u, int v)

{

    Node[cnt].u = u;

    Node[cnt].v = v;

    Node[cnt].next = head[u];

    head[u] = cnt++;

}

void add(int u, int v)

{

    add_(u, v);

    add_(v, u);

}

void dfs(int u, int fa)

{

    pre[u] = lowlink[u] = ++dfs_clock;

    S.push(u);

    for(int i=; i<G[u].size(); i++)

    {

        int v = G[u][i];

        if(v == fa) continue;

        if(!pre[v])

        {

            dfs(v, u);

            lowlink[u] = min(lowlink[u], lowlink[v]);

        }

        else if(!sccno[v])

            lowlink[u] = min(lowlink[u], pre[v]);

    }

    if(lowlink[u] == pre[u])

    {

        scc_cnt++;

        for(;;)

        {

            int x = S.top(); S.pop();

            sccno[x] = scc_cnt;

            if(x == u) break;

        }

    }

}

void init()

{

    dfs_clock = scc_cnt = cnt = ;

    mem(sccno, );

    mem(pre, );

    mem(head, -);

}

void bfs(int u)

{

    mem(vis, );

    mem(d, );

    queue<int> Q;

    Q.push(u);

    vis[u] = ;

    d[u] = ;

    maxway = , pos = u, ans = ;

    while(!Q.empty())

    {

        int u = Q.front(); Q.pop();

        for(int i=head[u]; i!=-; i=Node[i].next)

        {

            int v = Node[i].v;

            if(!vis[v])

            {

                vis[v] = ;

                d[v] = d[u] + ;

                if(d[v] > maxway)

                    maxway = d[v], pos = v;

                Q.push(v);

            }

        }

    }

}

int main()

{

    init();

    cin>> n >> m;

    int u, v;

    for(int i=; i<m; i++)

    {

        cin>> u >> v;

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs(, -);

//    cout<< scc_cnt <<endl;

    for(int i=; i<=n; i++)

    {

        for(int j=; j<G[i].size(); j++)

        {

            int v = G[i][j];

            if(sccno[i] != sccno[v])

            {

            //    cout<< i << "  " << v <<endl;

            //    w[i][v] = w[v][i] = 1;

                if(!w[sccno[i]][sccno[v]])

                    w[sccno[i]][sccno[v]] = w[sccno[i]][sccno[v]] = , add(sccno[i], sccno[v]);

            }

        }

    }

    bfs();

    bfs(pos);

    cout<< maxway <<endl;

    return ;

}