本文共 1959 字，大约阅读时间需要 6 分钟。
题意： 给定一张有向图。找出全部强连通分量，并输出。
思路：有向图的强连通分量用Tarjan算法，然后用map映射，便于输出，注意输出格式。
代码：
#include #include #include #include #include using namespace std;const int MAXN = 2000;const int MAXM = 50000;struct Edge{ int to, next;}edge[MAXM];int head[MAXN], tot;int Low[MAXN], DFN[MAXN], Stack[MAXN], Belong[MAXN];int Index, top;int scc;bool Instack[MAXN];int num[MAXN];int n, m, cnt;map sTon;map nTos; void init() { tot = cnt = 0; memset(head, -1, sizeof(head)); sTon.clear(); nTos.clear();}void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;}void Tarjan(int u) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for (int i = head[u]; i != -1; i = edge[i].next) { v = edge[i].to; if (!DFN[v]) { Tarjan(v); if (Low[u] > Low[v]) Low[u] = Low[v]; } else if (Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v]; } if (Low[u] == DFN[u]) { scc++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = scc; num[scc]++; } while (v != u); }}void solve() { memset(Low, 0, sizeof(Low)); memset(DFN, 0, sizeof(DFN)); memset(num, 0, sizeof(num)); memset(Belong, 0, sizeof(Belong)); memset(Stack, 0, sizeof(Stack)); memset(Instack, false, sizeof(Instack)); Index = scc = top = 0; for (int i = 1; i <= n; i++) if (!DFN[i]) Tarjan(i);}int main() { int t = 0; while (scanf("%d%d", &n, &m)) { if (n == 0 && m == 0) break; init(); string s1, s2; for (int i = 0; i < m; i++) { cin >> s1 >> s2; if (sTon.find(s1) == sTon.end()) { cnt++; sTon[s1] = cnt; nTos[cnt] = s1; } if (sTon.find(s2) == sTon.end()) { cnt++; sTon[s2] = cnt; nTos[cnt] = s2; } addedge(sTon[s1], sTon[s2]); } if (t) printf("\n"); printf("Calling circles for data set %d:\n", ++t); solve(); for (int i = 1; i <= scc; i++) { int flag = 0; for (int u = 1; u <= n; u++) { if (Belong[u] == i) { if (!flag) { cout << nTos[u]; flag = 1; } else cout << ", " << nTos[u]; } } printf("\n"); } } return 0;}
转载地址：http://yfdra.baihongyu.com/