https://vjudge.net/problem/POJ-2117

tarjan终极模板

solve()：求桥

solve1()：求割点

solve2()：求去掉一个点后联通块数

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 10005;
const int maxm = 100005;
struct edge
{
    int to, next;
    bool cut;
}e[maxm];
int head[maxn], cnt;
int low[maxn], dfn[maxn], stk[maxn];
int indexx, top;
bool vis[maxn];
bool cut[maxn];
int add_block[maxn];//删除一个点后增加的联通块数
int bridge;
void addedge(int u, int v)
{
    e[cnt].to = v;
    e[cnt].cut = 0;
    e[cnt].next = head[u];
    head[u] = cnt ++;
}
void tarjan(int u, int pre)
{
    low[u] = dfn[u] = ++ indexx;
    stk[top ++] = u;
    vis[u] = 1;
    int son = 0;
    int pre_cnt = 0;
    for(int i = head[u]; ~i; i = e[i].next)
    {
        int v = e[i].to;
        if(v == pre && pre_cnt == 0)
        {
            pre_cnt ++;
            continue;
        }
        if(! dfn[v])
        {
            son ++;
            tarjan(v, u);
            if(low[u] > low[v])
                low[u] = low[v];
            if(low[v] > dfn[u])
            {
                bridge ++;
                e[i].cut = 1;
                e[i^1].cut = 1;
            }
            if(u != pre && low[v] >= dfn[u])
            {
                cut[u] = 1;
                add_block[u] ++;
            }
        }
        else if(low[u] > dfn[v])
            low[u] = dfn[v];
    }
    if(u == pre && son > 1) cut[u] = 1;
    if(u == pre) add_block[u] = son - 1;
    vis[u] = 0;
    top --;
}
map<int, int> mapit;//判断重边
inline bool isHash(int u, int v)
{
    if(u == v) return 1;
    if(mapit[u*maxn+v]) return 1;
    if(mapit[v*maxn+u]) return 1;
    mapit[u*maxn+v] = mapit[v*maxn+u] = 1;
    return 0;
}
void solve(int n)//桥
{
    memset(dfn, 0, sizeof(dfn));
    memset(vis, 0, sizeof(vis));
    memset(add_block, 0, sizeof(add_block));
    memset(cut, 0, sizeof(cut));
    indexx = top = 0;
    bridge = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(! dfn[i])
            tarjan(i, i);
    }
    printf("%d critical links\n", bridge);
    vector<pair<int, int> > ans;
    for(int u = 1; u <= n; u ++)
    {
        for(int i = head[u]; ~i; i = e[i].next)
        {
            if(e[i].cut && e[i].to > u)
            {
                ans.push_back(make_pair(u, e[i].to));
            }
        }
    }
    sort(ans.begin(), ans.end());
    int ansize = ans.size();
    for(int i = 0; i < ansize; i ++)
    {
        printf("%d - %d\n", ans[i].first - 1, ans[i].second - 1);
    }
    printf("\n");
}
void solve1(int n)//割点
{
    memset(dfn, 0, sizeof(dfn));
    memset(vis, 0, sizeof(vis));
    memset(add_block, 0, sizeof(add_block));
    memset(cut, 0, sizeof(cut));
    indexx = top = 0;
    bridge = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(! dfn[i])
            tarjan(i, i);
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++)
        if(cut[i]) ans ++;
    printf("%d\n", ans);
}
void solve2(int n)//删除一个点后，图中最多有多少个联通块
{
    memset(dfn, 0, sizeof(dfn));
    memset(vis, 0, sizeof(vis));
    memset(add_block, 0, sizeof(add_block));
    memset(cut, 0, sizeof(cut));
    indexx = top = 0;
    bridge = 0;
    int num = 0;//记录本来的联通块数
    for(int i = 1; i <= n; i ++)
    {
        if(! dfn[i])
        {
            tarjan(i, i);
            num ++;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++)
        ans = max(ans, num + add_block[i]);
    printf("%d\n", ans);
}
int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF && (n + m))
    {
        memset(head, -1, sizeof(head));
        cnt = 0;
        int u, v;
        //mapit.clear();
        while(m --)
        {
            scanf("%d%d", &u, &v);
            u ++, v ++;
            addedge(u, v);
            addedge(v, u);
        }
        solve2(n);
    }
    return 0;
}