tarjan算法时间复杂度： O ( N + M ) O(N+M) O(N+M) 一.缩点 POJ1236 Network of Schools
#include <cstdio> #include <vector> #define max(x, y) ((x)>(y)?(x):(y)) #define min(x, y) ((x)<(y)?(x):(y)) #define pb push_back using namespace std; const int MAXN = 105; int dfn[MAXN], low[MAXN], idx; int stk[MAXN], top; int belong[MAXN], sum; //记录强连通分量的集合 int in[MAXN], out[MAXN]; //记录每个强连通分量的入度和出度 bool instk[MAXN]; vector<int> es[MAXN]; void tarjan(int u){ dfn[u] = low[u] = ++idx; stk[++top] = u; instk[u] = true; for (int i = 0; i < es[u].size(); i++){ int v = es[u][i]; if (dfn[v] == 0){ tarjan(v); low[u] = min(low[u], low[v]); }else if (instk[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]){ //将n个点缩成sum个强连通分量 int v; belong[u] = ++sum; instk[u] = false; do{ v = stk[top--]; belong[v] = sum; instk[v] = false; }while (u != v); } } int main(){ int n; scanf("%d", &n); for (int u = 1, v; u <= n; u++){ while (~scanf("%d", &v)){ if (v == 0) break; es[u].pb(v); } } for (int u = 1; u <= n; u++) if (dfn[u] == 0) tarjan(u); for (int u = 1; u <= n; u++){ for (int i = 0; i < es[u].size(); i++){ int v = es[u][i]; if (belong[u] != belong[v]) in[belong[v]]++, out[belong[u]]++; } } int a = 0, b = 0; for (int i = 1; i <= sum; i++){ if (in[i] == 0) a++; else if (out[i] == 0) b++; } if (sum == 1) printf("1\n0\n"); else printf("%d\n%d\n", a, max(a, b)); return 0; }二.割点 UVA315 Network
#include <cstdio> #include <cstring> #include <vector> #define max(x, y) ((x)>(y)?(x):(y)) #define min(x, y) ((x)<(y)?(x):(y)) #define pb push_back #define MEM(x, y) memset((x), (y), sizeof(x)) using namespace std; const int MAXN = 105; int dfn[MAXN], low[MAXN], idx; bool is[MAXN]; vector<int> es[MAXN]; inline void init(){ for (int i = 0; i < MAXN; i++) es[i].clear(); MEM(dfn, 0); MEM(low, 0); MEM(is, false); idx = 0; } void tarjan(int u, int root){ dfn[u] = low[u] = ++idx; int child = 0; for (int v: es[u]){ if (dfn[v] == 0){ child++; tarjan(v, root); low[u] = min(low[u], low[v]); //两种情况1.根节点且孩子>=2; // 2.非根节点且有一个孩子能回溯的最早的low不超过自己dfn的值. if (u==root && child>=2) is[u] = true; else if (u!=root && low[v]>=dfn[u]) is[u] = true; }else low[u] = min(low[u], dfn[v]); } } int main(){ int n, u, v; char c; while (~scanf("%d", &n)){ if (n == 0) break; init(); while (~scanf("%d%c", &u, &c)){ if (u == 0) break; while (~scanf("%d%c", &v, &c)){ es[u].pb(v); es[v].pb(u); if (c == '\n') break; } } for (int i = 1; i <= n; i++) if (dfn[i] == 0) tarjan(i, i); int ans = 0; for (int i = 1; i <= n; i++) if(is[i]) ans++; printf("%d\n", ans); } return 0; }三.桥（割边） UVA796 Critical Links
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #define max(x, y) ((x)>(y)?(x):(y)) #define min(x, y) ((x)<(y)?(x):(y)) #define MEM(x, y) memset((x), (y), sizeof(x)) #define pb push_back #define mp make_pair using namespace std; typedef pair<int, int> PII; const int MAX = 1e4+10; struct Edge{ int v, next; Edge(){} }es[MAX]; int dfn[MAX], low[MAX], idx; int head[MAX], k; vector<PII> ans; bool cmp(const PII a, const PII b){ if (a.first == b.first) return a.second < b.second; return a.first < b.first; } inline void init(){ ans.clear(); MEM(dfn, 0); MEM(low, 0); MEM(head, 0); idx = k = 0; } inline void add(int u, int v){ es[++k].next = head[u]; es[k].v = v; head[u] = k; } void tarjan(int u, int pre){ dfn[u] = low[u] = ++idx; for (int i = head[u]; i; i = es[i].next){ int v = es[i].v; if (v == pre) continue; //防止回边 if (dfn[v] == 0){ tarjan(v, u); low[u] = min(low[u], low[v]); //桥的判断条件 if (low[v] > dfn[u]) ans.pb(mp(min(u, v), max(u, v))); }else low[u] = min(low[u], dfn[v]); } } int main(){ int n, u, v, num; while (~scanf("%d", &n)){ init(); for (int i = 0; i < n; i++){ scanf("%d (%d)", &u, &num); while (num--){ scanf("%d", &v); add(u, v); } } for (int i = 0; i < n; i++) if (dfn[i] == 0) tarjan(i, -1); if (!ans.empty()) sort(ans.begin(), ans.end(), cmp); printf("%d critical links\n", ans.size()); for (auto a: ans) printf("%d - %d\n", a.first, a.second); printf("\n"); } return 0; }