图论割点模板

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;


const int N = 109;
int low[N], num[N], dfn;
bool iscut[N];
vector<int>G[N];
//num只是记录跑到这个点的“时间”，不必修改
void dfs(int u, int fa)
{
	num[u] = low[u] = ++dfn;
	int child = 0;
	for (int i = 0; i < G[u].size(); i++)
	{
		int v = G[u][i];
		if (!num[v])
		{
			child++;
			dfs(v, u);
			//为什么不用fa？因为这只是“直系”！要考虑的不是祖先，不是并查集之类的问题，
			low[u] = min(low[u], low[v]);
			if (low[u] <= low[v] and u != 1)
				//为什么加上u！=1？因为u是1的情况已经在下面讨论了，防止只有1个孩子的1号节点也被算
				iscut[u] = 1;
		}
		else if (num[v] < num[u] and v != fa)
			//处理回退边，就是越级相连的点，为什么要加v！=fa？因为无向图初始化的时候两边都会进vector
			low[u] = min(low[u], num[v]);
	}
	if (u == 1 and child >= 2)
		iscut[1] = 1;
}
int main()
{
	int ans, n;
	while (scanf("%d", &n) != -1)
	{
		if (n == 0)break;
		memset(low, 0, sizeof(low));
		memset(num, 0, sizeof(num));
		dfn = 0;
		for (int i = 0; i <= n; i++)G[i].clear();
		int a, b;
		while (scanf("%d", &a) && a)
		{
			while (getchar() != '\n')
			{
				scanf("%d", &b);
				G[a].push_back(b);
				G[b].push_back(a);
			}
		}
		memset(iscut, 0, sizeof(iscut));
		ans = 0;
		dfs(1, 1);
		for (int i = 1; i <= n; i++)ans += iscut[i];
		cout << ans;
	}
	return 0;
}