# 割点算法

## 割点算法Tarjan POJ 2117 Electricity

``````
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int N = 10005;
const int M = 30005;
int tot;
int to[M], nxt[M], head[M]; // graph 链式前向星存储方式
int dfn[N];
int low[N];
int ts;
int n, m;
int bp, cnt;
int root;
void add(int u, int v){ // connstruct graph;
++tot;
to[tot] = v;
}
void tarjan(int u){
// cout << u << ' ';
int subtree = 0;
dfn[u] = low[u] = ++ts;
for(int i = head[u]; i; i = nxt[i]){
int v = to[i];

if(dfn[v]) low[u] = min(low[u], dfn[v]);
else{
tarjan(v);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) ++subtree;; // 节点u是割点，且割点对应的子节点v是在一个被分割子树中
}
}
if( u != root) ++subtree;
bp = max(bp, subtree);
}
int main(){
while(scanf("%d%d", &n, &m), n || m){
ts = tot = bp = cnt = 0;
memset(dfn, 0x00, sizeof dfn);
memset(low, 0x00, sizeof low);
int a ,b;
while(m--){
scanf("%d%d", &a, &b);
}

for(root = 0; root < n; ++root){
if(!dfn[root]){
tarjan(root);
cnt++;
}
}
printf("%d\n", cnt + bp - 1);
}
return 0;
}

``````

## 补充知识点

``````#!/bin/sh
g++ \$1 -o ./a.out
./a.out < input  > myoutput
diff myoutput output -s -u``````
{"ft_lang_label":"__label__zh","ft_lang_prob":0.52934927,"math_prob":0.9992405,"size":1604,"snap":"2021-43-2021-49","text_gpt3_token_len":916,"char_repetition_ratio":0.090625,"word_repetition_ratio":0.0,"special_character_ratio":0.37157106,"punctuation_ratio":0.21661721,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9972448,"pos_list":[0,1,2],"im_url_duplicate_count":[null,2,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-18T19:59:41Z\",\"WARC-Record-ID\":\"<urn:uuid:fb8987a8-fc8e-4886-8ceb-b85842248009>\",\"Content-Length\":\"42071\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:101ce11f-2bb3-49bc-9b67-36a4c509da7d>\",\"WARC-Concurrent-To\":\"<urn:uuid:b4cea976-5482-4dde-bd74-3a7c11eb0569>\",\"WARC-IP-Address\":\"185.199.111.153\",\"WARC-Target-URI\":\"https://blog.come2rss.xyz/2021/05/09/shua-ti-shu-ju-jie-gou-tu-ge-dian-suan-fa/\",\"WARC-Payload-Digest\":\"sha1:PJ7G2PRWTBGVMWJU5UH34FS4IJJVB23S\",\"WARC-Block-Digest\":\"sha1:BEOIRXPGKSXIWKB7P5SIGNHKNX7R7Z4F\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323585209.43_warc_CC-MAIN-20211018190451-20211018220451-00264.warc.gz\"}"}