POJ2117(Electricity)

题目传送门

题意

题目说了一堆废话，简单直白一点就是求割点，删除哪个点之后连通分量最多(被删除的哪个点不算)，最开始给的图可能就是一个不联通的图，最多有1万个点，边数不知道多少。

思路

1. 由于图可能不连通所以放在循环里，对每个没有时间序的点跑tarjan求割点，每跑一次tarjan就有一个联通分量。
2. 枚举每一个点，计算删除该点下的连通分量数目找到最大。
3. 计算联通分量直接在tarjan模板上做修改，但是要注意根节点和非根节点的连通块数区别：根节点的连通块是孩子数目 - 1，非根节点直接统计就可以。
4. 由于边不知道是多少，防止链式前向星边数过大采用vector模拟邻接表存图，反正重边无影响对割点不影响。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
const int maxn = 10005;
vector<int>e[maxn];
int dfn[maxn];
int low[maxn];
int s[maxn];
int root,cnt;
inline void clear_set()
{
	for(int i = 0;i < maxn;i++){
		e[i].clear();
	}
	cnt = 0;
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(s,0,sizeof(s));
}
inline void tarjan(int x,int fx)
{
	dfn[x] = low[x] = ++cnt;
	int son = 0;
	for(int i = 0;i < e[x].size();i++){
		int y = e[x][i];
		if(!dfn[y]){
			son++;
			tarjan(y,x);
			low[x] = min(low[x],low[y]);
			if(low[y] >= dfn[x] && x != root){
				s[x]++;
			}
		}
		else if(y != fx && dfn[y] < dfn[x]){
			low[x] = min(low[x],dfn[y]);
		}
	}
	if(x == root){
		s[x] = son - 1;
	}
}
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m)){
		if(n == 0 && m == 0)	break;
		clear_set();
		for(int i = 0;i < m;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			e[x].push_back(y);
			e[y].push_back(x);
		}
		int sum = 0;
		for(int i = 0;i < n;i++){
			if(!dfn[i]){
				root = i;
				sum++;				//连通分量数目
				tarjan(i,-1);
			}	
		}
		int ans = 0;
		for(int i = 0;i < n;i++){
			ans = max(ans,sum+s[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}

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