無向連通圖的關(guān)節(jié)點(diǎn)：
1、樸素算法：枚舉+DFS，O(N^3)。
2、Robert Tarjan的Tarjan算法。O(N^2)
Tarjan算法是基于對(duì)圖深度優(yōu)先搜索的算法，每個(gè)強(qiáng)連通分量為搜索樹中的一棵子樹。搜索時(shí)，把當(dāng)前搜索樹中未處理的節(jié)點(diǎn)加入一個(gè)堆棧，回溯時(shí)可以判斷棧頂?shù)綏Ｖ械墓?jié)點(diǎn)是否為一個(gè)強(qiáng)連通分量。 定義DFN(u)為節(jié)點(diǎn)u搜索的次序編號(hào)(時(shí)間戳)，Low(u)為u或u的子樹能夠追溯到的最早的棧中節(jié)點(diǎn)的次序號(hào)。 當(dāng)DFN(u)=Low(u)時(shí)，以u(píng)為根的搜索子樹上所有節(jié)點(diǎn)是一個(gè)強(qiáng)連通分量。
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;
}