強連通：在有向圖中，如果Vx能到達Vy，且Vy也能到達Vx，說明它們兩個點強連通，
強連通分量：在有向圖中，存在一個極大子圖，該子圖中任意兩點都是強連通，
#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 = 1e4 + 10; int dfn[N]; //時間戳 int low[N]; //能到達最早點 int s[N]; //堆疊 int ins[N]; //是否在堆疊內 int scc_no[N];//屬于哪個scc int scc_cnt[N]; //該scc有幾個點 vector<int > scc[N];//縮點 vector<int > E[N]; //邊 vector<int > new_E[N];//縮點后的圖 int SCC; //第幾個scc int tim;//dfs序號 int top;//堆疊頂 int n, m; //點數 邊數 //時間復雜度 O(m) void init(int n){ for(int i = 1; i <= n; ++i){ dfn[i] = low[i] = ins[i] = 0; scc_cnt[i] = 0; scc_no[i] = 0; scc[i].clear(); E[i].clear(); new_E[i].clear(); } SCC = tim = top = 0; } void tarjan(int now){ dfn[now] = low[now] = ++tim; ins[now] = 1; s[top++] = now; for(auto to : E[now]){ if(!dfn[to]){ tarjan(to); low[now] = min(low[now], low[to]); }else if(ins[to]){ //側邊，形成環 low[now] = min(low[now], dfn[to]); } } if(dfn[now] == low[now]){ int sum = 0; //該scc的點數 ++SCC;//第幾個scc int tmp;//暫存點 do{ tmp = s[--top];//取點 ins[tmp] = 0;//出堆疊 ++sum;//點數++ scc_no[tmp] = SCC;//屬于哪個scc scc[SCC].pb(tmp);//放入這個連通圖，縮點 }while(tmp != now); scc_cnt[SCC] = sum;//該scc的點數 } } void show_info(){ //每個點屬于哪個scc cout << endl << "-------------------" << endl; for(int i = 1; i <= n; ++i){ printf("id = %d scc_no = %d\n", i, scc_no[i]); } //每個scc包含幾個點 cout << endl << "-------------------" << endl; for(int i = 1; i <= SCC; ++i){ printf("SCC = %d cnt = %d\n", i, scc_cnt[i]); //這個scc中點的資訊 printf("have point : "); for(auto poi : scc[i]){ printf("(%d) ", poi); } cout << endl << endl; } cout << endl << "-------------------" << endl; //新圖的邊 for(int i = 1; i <= SCC; ++i){ printf("id = %d: to : ", i); for(auto v : new_E[i]){ printf("(%d) ", v); }printf("\n"); } cout << endl << "-------------------" << endl; } 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); } //可能不是一個連通圖 for(int now = 1; now <= n; ++now){ if(!dfn[now]){ tarjan(now); } } //新圖建邊 for(int now = 1; now <= n; ++now){ for(auto to : E[now]){ if(scc_no[now] != scc_no[to]){ new_E[scc_no[now]].pb(scc_no[to]); } } } //tarjan（）過后的資訊展示 show_info(); } } int main(){ solve(); //cout << "not error" << endl; return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/47543.html
標籤：其他