Tarjan 算法判断图是否为强连通图

#include\u003cbits\u002Fstdc++.h\u003e\nusing namespace std;\n\nconst int MAXN = 1919 + 810;\n\nint n, m, tot, head[MAXN]; pair\u003cint, int\u003e edge[MAXN * MAXN]; \nvoid addEdge(int u, int v) {\n edge[++tot] = {v, head[u]};\n head[u] = tot;\n} \nint top, cnt, dfc, dfn[MAXN], low[MAXN], stck[MAXN]; bool vis[MAXN]; \nvoid tarjan(int u) {\n dfn[u] = low[u] = ++dfc;\n stck[++top] = u;\n vis[u] = true;\n for(int i = head[u]; i; i = edge[i].second) {\n int v = edge[i].first;\n if(!dfn[v])\n tarjan(v), low[u] = min(low[u], low[v]);\n else if(vis[v])\n low[u] = min(low[u], low[v]);\n }\n if(dfn[u] == low[u]) {\n cnt++;\n for(int v = stck[top]; top--; v = stck[top]) {\n vis[v] = false;\n if(u == v) return ;\n }\n }\n} \nint main() {\n while(scanf("%d%d", &n, &m) && (n || m)) {\n memset(head, 0, sizeof head);\n tot = 0;\n while(m--) {\n int u, v;\n scanf("%d%d", &u, &v);\n int op;\n scanf("%d", &op);\n if(op == 1) addEdge(u, v);\n else addEdge(u, v), addEdge(v, u);\n }\n memset(dfn, 0, sizeof dfn);\n memset(low, 0, sizeof low);\n memset(vis, false, sizeof vis);\n cnt = dfc = top = 0;\n for(int i = 1; i <= n && cnt < 2; i++) {\n if(!dfn[i])\n tarjan(i);\n }\n printf("%d\n", cnt == 1);\n }\n return 0;\n}