點雙連通分量：在一個無向圖中，存在一個極大子圖，洗掉任意一個節點之后該圖仍然是一個連通圖，
割點：在一個無向圖中，存在一個節點，洗掉這個節點之后，該無向圖會被分為若干個連通圖（個數大于一），則該點為割點，
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <queue> #include <map> using namespace std; #define ll long long #define pb push_back #define fi first #define se second const int N = 2e4 + 10; int dfn[N]; //時間戳 int low[N]; //能到達最早點 int cut[N]; //是否是割點 vector<int > E[N]; //邊 int tim;//dfs序號 int root; //每個連通圖的出發點 int cut_cnt; //割點數量 int n, m; //點數 邊數 //時間復雜度 O(m) //割點條件 //(1)該點為最初點root，且該點之下至少存在左圖和右圖 //(2)該點不u為root，但是該點之后的點無法到達u之前的點 void init(int n){ for(int i = 1; i <= n; ++i){ dfn[i] = low[i] = 0; cut[i] = 0; E[i].clear(); } tim = cut_cnt = 0; } void tarjan(int now, int pre){ dfn[now] = low[now] = ++tim; int son = 0;//圖個數 for(auto to : E[now]){ if(to == pre) continue; if(!dfn[to]){ ++son; tarjan(to, now); low[now] = min(low[now], low[to]); //(2)該點不u為root，但是該點之后的點無法到達u之前的點 if(now != root && dfn[now] <= low[to]) cut[now] = 1; }else low[now] = min(low[now], dfn[to]); } //(1)該點為最初點root，且該點之下至少存在左圖和右圖 if(now == root && son > 1) cut[now] = 1; } void show_info(){ //割點數量 printf("\ncut point 's number = %d\n", cut_cnt); //割點資訊 printf("they' re : "); for(int i = 1; i <= n; ++i){ if(cut[i]) printf("(%d) ", i); } printf("\n\n"); } void solve(){ while(~scanf("%d%d", &n, &m)){ //scanf("%d%d", &n, &m); //初始化每組資料 init(n); //讀邊 for(int i = 1; i <= m; ++i){ int u, v; scanf("%d%d", &u, &v); E[u].pb(v); E[v].pb(u); } //可能不是一個連通圖 for(int now = 1; now <= n; ++now){ if(!dfn[now]){ root = now; //這樣可以防止自環的情況 tarjan(now, now); } } //統計割點個數 for(int i = 1; i <= n; ++i){ if(cut[i]) ++cut_cnt; } show_info(); } } int main(){ solve(); //cout << "not error" << endl; return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/47549.html
標籤：其他
上一篇：二叉鏈的基本操作
下一篇：分享經典的動態規劃問題（一）