先了解一下每个名词的含义

无向图：没有方向的图
无向连通图：图中任意两节点可互相到达的无向图
无向非连通图：不是无向连通图
无相连通分量：无向非连通图中的最大连通子图
割点：删掉这个点就不连通
割边：删掉这个边就不连通
强联通有向图：任意两点可以到达的有向图
弱连通有向图：如果忽略边的方向是一个无向连通图
强联通分量（SCC）：非强连通图的极大连通子图

对于求无向图中的割点和割边

为什么有割点和非割点之分，那就是由于无向图连通有环，环中的点自然不是割点，如果无向连通图要是树的话，那么所有点就都是割点了

对于Tarjan算法，则是选择一个为根节点进行dfs搜索，用dfn数组存储每个节点出现时间（时间从1开始，0代表没搜过)

如果该图中有环那么该环中一定有first（最早出现的节点）和last（最晚出现的节点），而且last与fisrt有边能直接相连，当last搜寻下一个节点时便会搜到first

这时需要一个low数组存储每个点能搜索到的最早出现的时间，只有对于环中last搜到fisrt时，low数组能变小，而且会让从fisrt->last这条树链上的所有点i，使得low[i]=min(low[i],dfn[first])（代码中应该是low[u]=min(low[u],low[v])）

搜完所有点以后

若求割点每个点可以分为根节点和不是根节点

对于根节点，若有两个子节点那么该点即是割点（对于如何判断有几个子节点，在搜索时用一个fa[]数组存好由谁转移过来的，最后以判断有几个是由根节点转换的即可)

对于不是根节点i,若low[i]>=dfn[fa[i]]则该点父亲是割点（因为该点不通过该点与父亲的边最多只能搜到父亲节，那么删掉父亲节点，该点则不能搜到父亲以上节点）

若求割边，只需要搜每个不是根节点的点i，若low[i]>dfn[fa[i]]那么该点与父亲连的边为割边（因为若该点所能搜到的最早出现的点也比父亲出现的晚，说明该点不能搜到父亲上面的点）

代码如下

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
int dfn[1005],low[1005],fa[1005];
bool vis[1005];
vector<int>G[1005];
int cnt;
void tarjan(int u)
{
    dfn[u]=low[u]=++cnt;
    int i,j;
    for(i=0; i<G[u].size(); i++)
    {
        int v=G[u][i];
        if(dfn[v]==0)
        {
            fa[v]=u;
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else
            low[u]=min(low[u],dfn[v]);
    }
}
int gedian(int n)
{
    int num=0;
    memset(vis,false,sizeof(vis));
    int i,j,fu;
    for(i=2; i<=n; i++)
    {
        fu=fa[i];
        if(fu==1)
            num++;
        else
        {
            if(low[i]>=dfn[fu])
                vis[fu]=true;
        }
    }
    if(num>=2)
        vis[1]=true;
    int sum=0;
    for(i=1; i<=n; i++)
    {
        if(vis[i])
            sum++;
    }
    return sum;
}
int gebian(int n)
{
    int i,j,sum=0,fu;
    for(i=1;i<=n;i++)
    {
        fu=fa[i];
        if(fu>0&&low[i]>dfn[fu])
            sum++;
    }
    return sum;
}
int main()
{
    int n,m;
    while(scanf(“%d %d”,&n,&m)!=EOF)
    {
        int i,j;
        for(i=1; i<=n; i++)
            G[i].clear();
        int x,y;
        for(i=0; i<m; i++)
        {
            scanf(“%d %d”,&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        memset(dfn,0,sizeof(dfn));
        cnt=0;
        memset(fa,0,sizeof(fa));
        tarjan(1);

    }
}
跑一遍taijan以后有向图变成一棵树，对于原图环中一定被舍掉，但恰恰由于这条边改变了low值，因为树都是从上指向下，只有这条边往上指了，使得
该边下边点low值可以变成上边点dfn值
求割点
对于根如果有两棵子树则该点是割点
否则若该点u存在一个子节点v使得 low[v]>=dfn[u]则u为割点
求割边
对于某条边的子节点v父节点u存在 low[v]>dfn[u]则该边为割边