POJ1523(SPF)

题目传送门

题意

给定一个无向图，问有多少个割点。如果删掉这个割点这个连通图会变成几个连通块。

思路

tarjan求割点。求完割点之后用dfs去深度遍历每个点，dfs遍历或者bfs遍历，先标记割点。然后走过的点上标记，dfs几次就有几个连通块，输出答案即可。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1005;
const int maxm = 1e5+5;
struct edge{
	int to;
	int next;
}e[maxm];
int head[maxn];			
int dfn[maxn];		
int low[maxn];			
bool cut[maxn];
bool visited[maxn];
int tot,cnt,root;
inline void clear_set()
{
	cnt = tot = 0;
	memset(head,-1,sizeof(head));
	memset(cut,false,sizeof(cut));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
}
inline void addedge(int x,int y)
{
	e[tot].to = y;
	e[tot].next = head[x];
	head[x] = tot++;
}
inline void tarjan(int x,int fx)
{
	dfn[x] = low[x] = ++cnt;
	int child = 0;
	for(int i = head[x];~i;i = e[i].next){
		int y = e[i].to;
		if(!dfn[y]){
			child++;
			tarjan(y,x);
			low[x] = min(low[x],low[y]);
			if(low[y] >= dfn[x] && x != root){
				cut[x] = true;
			}
		}
		else if(dfn[y] < dfn[x] && y != fx){
			low[x] = min(low[x],dfn[y]);
		}
	}
	if(child > 1 && x == root){
		cut[root] = true;
	}
}
inline void dfs(int x)
{
	for(int i = head[x];~i;i = e[i].next){
		int y = e[i].to;
		if(!visited[y]){
			visited[y] = true;
			dfs(y);
		}
	}
}
int main()
{
	int x,y,n,k = 1;
	while(~scanf("%d",&x) && x){
		scanf("%d",&y);
		clear_set();
		n = max(x,y);
		addedge(x,y);	addedge(y,x);
		while(~scanf("%d",&x) && x){
			scanf("%d",&y);
			n = max(n,max(x,y));
			addedge(x,y);	addedge(y,x);
		}
		for(int i = 1;i <= n;i++){
			if(!dfn[i]){
				root = i;
				tarjan(i,-1);
			}
		}
		int res = 0;
		if(k > 1){
			printf("\n");
		}
		printf("Network #%d\n",k++);
		for(int i = 1;i <= n;i++){
			if(cut[i]){
				int ans = 0;
				res++;
				memset(visited,false,sizeof(visited));
				visited[i] = true;
				for(int k = 1;k <= n;k++){
					if(!visited[k]){
						dfs(k);
						ans++;
					}
				}
				printf("  SPF node %d leaves %d subnets\n",i,ans);
			}
		}
		if(res == 0){
			printf("  No SPF nodes\n");
		}
	}
	return 0;
}

方法二：不过这道题上面的做法也可以过，但是还有更快的做法，因为两个连通分量之间最多只有一个点连接（割点），如果连接多个点自然也就没有割点了。所以在求割点的时候可以统计该割点下的连通分量数目。

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1005;
const int maxm = 1e5+5;
struct edge{
	int to;
	int next;
}e[maxm];
int head[maxn];
int dfn[maxn];
int low[maxn];
int s[maxn];
bool cut[maxn];
int tot,cnt,root;
bool flag;
inline void clear_set()
{
	flag = false;
	cnt = tot = 0;
	memset(head,-1,sizeof(head));
	memset(s,0,sizeof(s));
	memset(cut,false,sizeof(cut));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
}
inline void addedge(int x,int y)
{
	e[tot].to = y;
	e[tot].next = head[x];
	head[x] = tot++;
}
inline void tarjan(int x,int fx)
{
	dfn[x] = low[x] = ++cnt;
	int son = 0;
	for(int i = head[x];~i;i = e[i].next){
		int y = e[i].to;
		if(!dfn[y]){
			son++;
			tarjan(y,x);
			low[x] = min(low[x],low[y]);
			if((root == x && son > 1)||(low[y] >= dfn[x] && x != root)){
				flag = true;
				s[x]++;
				cut[x] = true;
			}
		}
		else if(dfn[y] < dfn[x] && y != fx){
			low[x] = min(low[x],dfn[y]);
		}
	}
	if(son > 1 && x == root){
		cut[root] = true;
	}
}
int main()
{
	int x,y,n,k = 1;
	while(~scanf("%d",&x) && x){
		scanf("%d",&y);
		clear_set();
		n = max(x,y);
		addedge(x,y);	addedge(y,x);
		while(~scanf("%d",&x) && x){
			scanf("%d",&y);
			n = max(n,max(x,y));
			addedge(x,y);	addedge(y,x);
		}
		for(int i = 1;i <= n;i++){
			if(!dfn[i]){
				root = i;
				tarjan(i,-1);
			}
		}
		int res = 0;
		if(k > 1){
			printf("\n");
		}
		printf("Network #%d\n",k++);
		if(!flag){
			printf("  No SPF nodes\n");
		}
		else{
			for(int i = 1;i <= n;i++){
				if(s[i] > 0){
					printf("  SPF node %d leaves %d subnets\n",i,s[i]+1);
				}
			}
		}
	}
	return 0;
}

愿你走出半生，归来仍是少年~