无向连通图的关节点：
1、朴素算法：枚举+DFS，O(N^3)。
2、Robert Tarjan的Tarjan算法。O(N^2)
Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。 定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。 当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。
SPF POJ 1523，ZOJ 1119
只想说自己是SB啊啊啊啊：
#include<stdio.h>
#include<string.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define maxn 1001
int nodes;
int tmpdfn;
int son;
int dfn[maxn];
int low[maxn];
int subnets[maxn];
bool Edge[maxn][maxn];
bool vis[maxn];
void dfs(int u)
{
for (int v=1;v<=nodes;v++)
{
if (Edge[u][v])
{
if (!vis[v])
{
vis[v]=1;
low[v]=dfn[v]=++tmpdfn;
dfs(v);
// Edge[v][u]=Edge[u][v]=0;
low[u]=min(low[u],low[v]);
if (low[v]>=dfn[u])
{
if (u!=1)
subnets[u]++;
else
son++;
}
}
else
{
low[u]=min(low[u],dfn[v]);
}
}
}
}
void init()
{
low[1]=dfn[1]=1;
tmpdfn=1;
son=0;
memset(vis,0,sizeof(vis));
vis[1]=1;
memset(subnets,0,sizeof(subnets));
}
int main()
{
int u,v;
int t=0;
while (1)
{
scanf("%d",&u);
if (u==0)
break;
scanf("%d",&v);
nodes=max(u,v);
memset(Edge,0,sizeof(Edge));
Edge[u][v]=Edge[v][u]=1;
while (1)
{
scanf("%d",&u);
if (u==0)
break;
scanf("%d",&v);
nodes=max(nodes,u);
nodes=max(nodes,v);
Edge[u][v]=Edge[v][u]=1;
}
if (t>0) printf("\n");
printf("Network #%d\n",++t);
init();
dfs(1);
if (son>1)
subnets[1]=son-1;
bool flag=0;
for (int i=1;i<=nodes;i++)
{
if (subnets[i]>0)
{
flag=1;
printf(" SPF node %d leaves %d subnets\n",i,subnets[i]+1);
}
}
if (!flag)
printf(" No SPF nodes\n");
}
return 0;
}